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$.