AT_kupc2017_h.Make a Potion

注 : 以下的中括号("[]"),例如 V[i] 的 [i] 为下标

将n种液体配制成11种化妆水。

第i类（ 1 ≤ i ≤ n ）液体体积 V[i]

一种液体的体积W[1] , W[2]……W[n]

使用后，化妆水的效果 ∑ W[i] × h[i]

但是，使用的体积必须是整数。

并且，有m个条件，第i个（ 1 ≤ i ≤ m ）条件如下。

如果第 a[i] 类液体的体积在 x[i] 以上，请求出使用液体满足第 b[i] 类液体的体积在 y[i] 以上必须使用的条件时的化妆水的最大效果值。

翻译提供者 : zhaojiazheng200439

zhaojiazheng200439

*输入由以下格式给出：

n n n   m m m 
v1 v_1 v1​   v2 v_2 v2​   ... ... ...   vn v_n vn​ 
h1 h_1 h1​   h2 h_2 h2​   ... ... ...   hn h_n hn​ 
a1 a_1 a1​   x1 x_1 x1​   b1 b_1 b1​   y1 y_1 y1​ 
a2 a_2 a2​   x2 x_2 x2​   b2 b_2 b2​   y2 y_2 y2​ 
: : : 
am a_m am​   xm x_m xm​   bm b_m bm​   ym y_m ym​ 

输出 : 在上述条件下你能获得的药剂的最大效力。

输入输出样例

输入#1

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

输出#1

700

输入#2

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

输出#2

-1200

输入#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

说明/提示

限制条件

· 输入全部为整数

· 1 ≤ n ≤ 1000

· 1 ≤ m ≤ 2000

· 1 ≤ v[i] ≤ 10 ^ 6 (1 ≤ i ≤ n)

· -10 ^ 6 ≤ h[i] ≤ 10 ^ 6 (1 ≤ i ≤ n)

· 1 ≤ a[i] , b[i] ≤ n (1 ≤ i ≤ m)

· 0 ≤ x[i] ≤ v[a[i]] (1 ≤ i ≤ m)

· 0 ≤ y[i] ≤ v[b[i]] (1 ≤ i ≤ m)

· 同一条件最多给出一次

示例说明1

第一种液体体积800，第二种液体体积10使用时的效果最大。

示例说明2

你必须使用体积至少为400的液体1。

示例说明4

有些答案会溢出32位整数。