Kyoto University Programming Contest 2017

H - Make a Potion


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 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 種類目の液体を体積 8002 種類目の液体を体積 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.


Source name

KUPC2017

Submit提出する