CF1989D Smithing Skill

题目描述

你在玩一款可以运行的著名电脑游戏，游戏中，你有许多能升级的技能。今天，你着重于铸造这个技能。你的策略是显然的：用材料锻造武器，并将其熔毁以返还部分材料。具体地，每次锻造和熔毁都可以提供 $1$ 点经验值。

有 $n$ 种可供锻造的武器，$m$ 种材料。

若要锻造第 $i$ 种武器，需耗费 $a_i$ 个 同种 材料，熔毁这把武器则返还 $b_i$ 个 制作所用的 材料。

初始你每种材料有 $c_i$ 个，你可以无限次的锻造和熔毁，每把武器均可以用任一种材料。

求你能获得的最大经验值。

输入格式

第一行输入整数 $n,m$（$1\le n,m \le 10^6$），为武器种数和材料种数。

第二行输入 $n$ 个数 $a_i$（$1 \le a_i \le 10^6$），为第 $i$ 种武器消耗材料数。

第三行输入 $n$ 个数 $b_i$（$1 \le b_i < a_i$）,为熔毁第 $i$ 种武器返回材料数。

第四行输入 $m$ 个数 $c_i$（$1\le c_i \le 10^9$），表示你最开始拥有 $c_i$ 个材料 $i$。

输出格式

一行，为你获得的最大经验值。

样例解释

第一个样例中可以按下列方式操作：

1. 用材料 $1$ 锻造武器 $1$。

2. 熔毁武器 $1$.

3. 重复操作 $1,2$ 一次。

4. 用材料 $1$ 锻造并熔毁武器 $3$。

5. 用材料 $3$ 锻造并熔毁武器 $3$。

6. 用材料 $1$ 锻造并熔毁武器 $4$。

7. 用材料 $3$ 锻造并熔毁武器 $5$。

最终 $c = [2,4,2]$，经验值为最大值 $12$。

Translated by uid $408071$.

输入输出样例 #1

输入 #1

5 3
9 6 7 5 5
8 4 5 1 2
10 4 7

输出 #1

12

输入输出样例 #2

输入 #2

3 4
10 20 20
0 0 0
9 10 19 20

输出 #2

8

输入输出样例 #3

输入 #3

1 5
3
1
1000000000 1000000000 1000000000 1000000000 1000000000

输出 #3

4999999990