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

In the first example, you can do the following: 1. craft one weapon of the $ 1 $ -st class from the $ 1 $ -st type of metal, spending $ 9 $ ingots; 2. melt that weapon, returning $ 8 $ ingots of the $ 1 $ -st metal type; 3. again, craft and melt one weapon of the $ 1 $ -st class from the $ 1 $ -st metal type; 4. craft and melt one weapon of the $ 3 $ -rd class from the $ 1 $ -st metal type; 5. craft and melt one weapon of the $ 3 $ -rd class from the $ 3 $ -rd metal type; 6. craft and melt one weapon of the $ 4 $ -th class from the $ 1 $ -st metal type; 7. craft and melt one weapon of the $ 5 $ -th class from the $ 3 $ -rd metal type; In the end you'll have $ c = [2, 4, 2] $ ingots left. In total, you've crafted $ 6 $ weapons and melted $ 6 $ weapons, gaining $ 12 $ experience points in total.