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](https://www.luogu.com.cn/user/415130)
输入格式
*输入由以下格式给出：
```cpp
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**
```cpp
2 2
1000 1800
1 -10
1 200 2 10
1 801 2 1000
```
**输出#1**
```cpp
700
```
**输入#2**
```cpp
1 4
500
-3
1 0 1 100
1 50 1 300
1 300 1 400
1 401 1 410
```
**输出#2**
```cpp
-1200
```
**输入#3**
```cpp
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**
```cpp
1445
```
**输入#4**
```cpp
1 1
1000000
1000000
1 0 1 0
```
**输出#4**
```cpp
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位整数。
说明/提示
### 制約
- 入力は全て整数である
- $ 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) $
- 同じ条件は複数回与えられない
### Sample Explanation 1
$ 1 $ 種類目の液体を体積 $ 800 $、$ 2 $ 種類目の液体を体積 $ 10 $ 使ったときの効力が最大です。
### Sample Explanation 2
$ 1 $ 種類目の液体を少なくとも体積 $ 400 $ 使わなければなりません。
### Sample Explanation 4
答えが $ 32 $ bit整数型に収まらない場合があります。