D. Кузнечное дело
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы играете в одну известную игру (которая «просто работает»), в которой у вас есть различные навыки, которые можно прокачивать. Сегодня вы сосредоточились на навыке «Кузнечное дело». Ваша тактика довольно проста: ковать оружие из слитков, а затем их переплавлять, чтобы вернуть часть материалов. Для простоты, каждый раз, когда вы создаете предмет, вы получаете $$$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 3
9 6 7 5 5
8 4 5 1 2
10 4 7
Выходные данные
12
Входные данные
3 4
10 20 20
0 0 0
9 10 19 20
Выходные данные
8
Входные данные
1 5
3
1
1000000000 1000000000 1000000000 1000000000 1000000000
Выходные данные
4999999990
Примечание

В первом тесте вы можете сделать следующее:

  1. создать одно оружие $$$1$$$-го класса из $$$1$$$-го типа металла, потратив $$$9$$$ слитков;
  2. переплавить это оружие, вернув $$$8$$$ слитков $$$1$$$-го типа металла;
  3. снова создать и переплавить одно оружие $$$1$$$-го класса из $$$1$$$-го типа металла;
  4. создать и переплавить одно оружие $$$3$$$-го класса из $$$1$$$-го типа металла;
  5. создать и переплавить одно оружие $$$3$$$-го класса из $$$3$$$-го типа металла;
  6. создать и переплавить одно оружие $$$4$$$-го класса из $$$1$$$-го типа металла;
  7. создать и переплавить одно оружие $$$5$$$-го класса из $$$3$$$-го типа металла;
В конце у вас останется $$$c = [2, 4, 2]$$$ слитков. Всего вы создали $$$6$$$ оружий и переплавили $$$6$$$ оружий, заработав в общей сложности $$$12$$$ очков опыта.