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