分数: 300 点
问题陈述
你正在复利 n 种液体变成药水。
液体体积 i (1 \leq i \leq n) is v_i.
当您使用 i-th (1 \leq i \leq n) 液体体积 w_i (0 \leq w_i \leq v_i) 对于每个 i,您获得 $Σ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
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- 位整数。 有