Вы играете в одну известную игру (которая «просто работает»), в которой у вас есть различные навыки, которые можно прокачивать. Сегодня вы сосредоточились на навыке «Кузнечное дело». Ваша тактика довольно проста: ковать оружие из слитков, а затем их переплавлять, чтобы вернуть часть материалов. Для простоты, каждый раз, когда вы создаете предмет, вы получаете \(1\) очко опыта, и каждый раз, когда вы переплавляете предмет, вы также получаете \(1\) очко опыта.
В игре есть \(n\) классов оружия, которые вы можете создать, и \(m\) типов металлических слитков.
Вы можете создать одно оружие \(i\)-го класса, затратив \(a_i\) слитков металла одного типа. Переплавка одного оружия \(i\)-го класса (которое вы ранее создали) возвращает вам \(b_i\) слитков металла, из которого оно было изготовлено.
У вас есть \(c_j\) слитков металла \(j\)-го типа, и вы знаете, что можете создать оружие любого класса из любого типа металла. Каждую комбинацию класса оружия и типа металла можно использовать любое количество раз.
Какое максимальное количество очков опыта вы можете заработать, создавая и переплавляя оружие?
Выходные данные
Выведите одно целое число — максимальное общее количество очков опыта, которое вы можете заработать, многократно создавая и переплавляя оружие.
Примечание
В первом тесте вы можете сделать следующее:
- создать одно оружие \(1\)-го класса из \(1\)-го типа металла, потратив \(9\) слитков;
- переплавить это оружие, вернув \(8\) слитков \(1\)-го типа металла;
- снова создать и переплавить одно оружие \(1\)-го класса из \(1\)-го типа металла;
- создать и переплавить одно оружие \(3\)-го класса из \(1\)-го типа металла;
- создать и переплавить одно оружие \(3\)-го класса из \(3\)-го типа металла;
- создать и переплавить одно оружие \(4\)-го класса из \(1\)-го типа металла;
- создать и переплавить одно оружие \(5\)-го класса из \(3\)-го типа металла;
В конце у вас останется
\(c = [2, 4, 2]\) слитков. Всего вы создали
\(6\) оружий и переплавили
\(6\) оружий, заработав в общей сложности
\(12\) очков опыта.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
9 6 7 5 5
8 4 5 1 2
10 4 7
|
12
|
|
2
|
3 4
10 20 20
0 0 0
9 10 19 20
|
8
|
|
3
|
1 5
3
1
1000000000 1000000000 1000000000 1000000000 1000000000
|
4999999990
|