Problem Description

We are trying to mix $ n $ types of liquids to create one potion.

The $ i $th type $(1 \leq i \leq n)$ of liquid has a volume of $ v_i $.

If we use volumes $ w_1 $, $ w_2 $, ..., $ w_n $ of each liquid, the potency of the potion will be $Σw_i \times h_i$.

However, the volumes used must be integers.

Additionally, there are $ m $ conditions, and the $ i $th $(1 \leq i \leq m)$ condition is as follows:

• If the $ a_i $th type of liquid is used with a volume of at least $ x_i $, then the $ b_i $th type of liquid must be used with a volume of at least $ y_i $.

Find the maximum potency of the potion when using the liquids while satisfying the conditions.

Input Format

The input is given from the standard input in the following format:

$ n $ $ m $ $ v_1 $ $ v_2 $ $ ... $ $ v_n $ $ h_1 $ $ h_2 $ $ ... $ $ h_n $ $ a_1 $ $ x_1 $ $ b_1 $ $ y_1 $ $ a_2 $ $ x_2 $ $ b_2 $ $ y_2 $ $ : $ $ a_m $ $ x_m $ $ b_m $ $ y_m $

Output Format

Output the maximum potency of the potion in one line to the standard output.

Sample Input and Output

Sample Input #1

2 2
1000 1800
1 -10
1 200 2 10
1 801 2 1000

Sample Output #1

700

Sample Input #2

1 4
500
-3
1 0 1 100
1 50 1 300
1 300 1 400
1 401 1 410

Sample Output #2

-1200

Sample Input #3

6 4
100 30 40 50 60 70
3 -5 2 -1 20 -10
1 20 2 20
3 11 2 25
2 24 4 10
3 30 1 80

Sample Output #3

1445

Sample Input #4

1 1
1000000
1000000
1 0 1 0

Sample Output #4

1000000000000

Notes/Hints

Constraints

• All inputs are integers.
• $1 \leq n \leq 1,000$
• $1 \leq m \leq 2,000$
• $1 \leq v_i \leq 10^6$ $(1 \leq i \leq n)$
• $-10^6 \leq h_i \leq 10^6$ $(1 \leq i \leq n)$
• $1 \leq a_i, b_i \leq n$ $(1 \leq i \leq m)$
• $0 \leq x_i \leq v_{a_i}$ $(1 \leq i \leq m)$
• $0 \leq y_i \leq v_{b_i}$ $(1 \leq i \leq m)$
• The same condition is not given multiple times.

Sample Explanation 1

The potency is maximized when using volume $ 800 $ of the $ 1 $st type of liquid and volume $ 10 $ of the $ 2 $nd type of liquid.

Sample Explanation 2

At least volume $ 400 $ of the $ 1 $st type of liquid must be used.

Sample Explanation 4

The answer may not fit within a 32-bit integer type.

见题面 Input 部分

见题面 Output 部分