← 返回题目列表

Codeforces · 1989/D

D. 锻造技能

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

您正在玩一款著名的电脑游戏(可以正常运行),您拥有各种可以升级的技能。今天,您重点学习了“锻造”技能。你的策略很明显:用锭锻造武器,然后将它们熔化以部分返还材料。为简单起见,每次创建物品时,您都会获得 $$$1$$$ 经验值,每次熔化物品时,您也会获得 $$$1$$$ 经验值。

你可以锻造 $$$n$$$ 类武器和 $$$m$$$ 种金属锭。

你可以花费 $$$a_i$$$ 相同类型的金属锭来制造一件 $$$i$$$ 级的武器。熔化 $$$i$$$ 级武器(你之前制作的)会返回 $$$b_i$$$ 其金属类型的锭。

你拥有 $$$j$$$ 类型的 $$$c_j$$$ 金属锭,并且你知道你可以用任何金属类型制作任何类别的武器。武器类别和金属类型的每种组合都可以使用任意多次。

通过制作和熔化武器可以获得的最大经验总量是多少?

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^6$$$) - 武器类别和金属类型的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$),其中 $$$a_i$$$ 是锻造第 $$$i$$$ 级武器所需的锭数。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i < a_i$$$),其中 $$$b_i$$$ 是你通过熔化你之前锻造的第 $$$i$$$ 级武器而返回的锭数。

第四行包含 $$$m$$$ 整数 $$$c_1, c_2, \dots, c_m$$$ ($$$1 \le c_j \le 10^9$$$) — 您拥有的相应金属类型的锭数。

输出

打印一个整数——通过反复锻造和熔化武器可以获得的最大总经验值。

示例

输入 #1

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

输出 #1

12

输入 #2

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

输出 #2

8

输入 #3

1 5
3
1
1000000000 1000000000 1000000000 1000000000 1000000000

输出 #3

4999999990

注意

在第一个示例中,您可以执行以下操作:

1.用$$$1$$$-st类型金属制作一件$$$1$$$-st级武器,花费$$$9$$$锭;
2. 熔化该武器,返回 $$$8$$$ 的 $$$1$$$-st 金属锭;
3. 再次从 $$$1$$$-st 金属类型中制作并熔化一件 $$$1$$$-st 级武器;
4. 从 $$$1$$$-st 金属类型中制作并熔化一件 $$$3$$$-rd 级武器;
5. 从 $$$3$$$-rd 金属类型中制作并熔化一件 $$$3$$$-rd 级武器;
6. 从$$$1$$$-st金属类型中制作并熔化一件$$$4$$$级武器;
7. 制作并熔化一件来自 $$$3$$$-rd 金属类型的 $$$5$$$-th 级武器;