/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
n 種類の液体を調合して 1 つのポーションを作ろうとしています。
i 種類目 (1 \leq i \leq n) の液体は体積が v_i あります。
液体をそれぞれ体積 w_1, w_2, ..., w_n 使うと、ポーションの効力は Σw_i \times h_i になります。
ただし、使う体積は整数でなければなりません。
さらに、m 個の条件があり、i 番目 (1 \leq i \leq m) の条件は以下の通りです。
- a_i 種類目の液体を体積 x_i 以上使うなら、b_i 種類目の液体を体積 y_i 以上使わなければならない
条件を満たすように液体を使ったときのポーションの効力の最大値を求めてください。
制約
- 入力は全て整数である
- 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)
- 同じ条件は複数回与えられない
入力
入力は以下の形式で標準入力から与えられる。
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
出力
ポーションの効力の最大値を標準出力に 1 行で出力せよ。
入力例1
2 2 1000 1800 1 -10 1 200 2 10 1 801 2 1000
出力例1
700
1 種類目の液体を体積 800、2 種類目の液体を体積 10 使ったときの効力が最大です。
入力例2
1 4 500 -3 1 0 1 100 1 50 1 300 1 300 1 400 1 401 1 410
出力例2
-1200
1 種類目の液体を少なくとも体積 400 使わなければなりません。
入力例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
出力例3
1445
入力例4
1 1 1000000 1000000 1 0 1 0
出力例4
1000000000000
答えが 32 bit整数型に収まらない場合があります。
Score : 300 points
Problem Statement
You are compounding n kinds of liquid into a potion.
The volume of liquid i (1 \leq i \leq n) is v_i.
When you use i-th (1 \leq i \leq n) liquid of volume w_i (0 \leq w_i \leq v_i) for each i, you earn the effectiveness of $Σw_i \times h_i.
Note that each volume you use must be an integer.
You also have m conditions and i-th condition (1 \leq i \leq m) is as follows.
- If you use liquid a_i of volume more than or equal to x_i, you must also use liquid b_i of volume more than or equal to y_i.
Find the maximum effectiveness of the potion you can obtain within the above conditions.
Constraints
- All input values 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 given at most once.
Input
Input is given from 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
Print the maximum effectiveness of the potion you can obtain within the above conditions.
Sample Input 1
2 2 1000 1800 1 -10 1 200 2 10 1 801 2 1000
Sample Output 1
700
You can get the maximum effectiveness by using liquid 1 of volume 800 and liquid 2 of volume 10.
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
You must use liquid 1 of volume at least 400.
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
Some answers overflow 32-bit integers.