Вы играете в одну известную игру (которая «просто работает»), в которой у вас есть различные навыки, которые можно прокачивать. Сегодня вы сосредоточились на навыке «Кузнечное дело». Ваша тактика довольно проста: ковать оружие из слитков, а затем их переплавлять, чтобы вернуть часть материалов. Для простоты, каждый раз, когда вы создаете предмет, вы получаете $$$1$$$ очко опыта, и каждый раз, когда вы переплавляете предмет, вы также получаете $$$1$$$ очко опыта.
В игре есть $$$n$$$ классов оружия, которые вы можете создать, и $$$m$$$ типов металлических слитков.
Вы можете создать одно оружие $$$i$$$-го класса, затратив $$$a_i$$$ слитков металла одного типа. Переплавка одного оружия $$$i$$$-го класса (которое вы ранее создали) возвращает вам $$$b_i$$$ слитков металла, из которого оно было изготовлено.
У вас есть $$$c_j$$$ слитков металла $$$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$$$) — количество слитков металла соответствующего типа, которые у вас есть.
Выведите одно целое число — максимальное общее количество очков опыта, которое вы можете заработать, многократно создавая и переплавляя оружие.
5 39 6 7 5 58 4 5 1 210 4 7
12
3 410 20 200 0 09 10 19 20
8
1 5311000000000 1000000000 1000000000 1000000000 1000000000
4999999990
В первом тесте вы можете сделать следующее:
Название |
---|