← 返回题目列表

AtCoder · kupc2017_h

H. 制作药水

中文机器翻译题面 查看原题

分数: 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- 位整数。 有