На границе миров открылся портал тёмных сил, и теперь всему миру грозит страшная угроза. Чтобы закрыть портал и спасти мир, нужно сперва победить \(n\) чудовищ, что последовательно вылезают из портала.
Справиться с этим может только волшебница Вика. Она владеет двумя магическими силами — магией воды и магией огня. За секунду Вика может сгенерировать \(w\) единиц водяной маны и \(f\) единиц огненной маны. Мана понадобится ей для создания заклинаний. Изначально у Вики \(0\) единиц водяной маны и \(0\) единиц огненной маны.
Каждое из \(n\) чудовищ, что вылезают из портала, имеет свою силу, выраженную натуральным числом. Чтобы победить \(i\)-е чудовище силы \(s_i\), нужно применить заклинание воды или заклинание огня не меньшей силы. Иначе говоря, Вика может потратить не менее единиц \(s_i\) водяной маны на заклинание воды, либо же не менее единиц \(s_i\) огненной маны на заклинание огня.
Вика умеет создавать и применять заклинания мгновенно. Вика может применять любое количество заклинаний каждую секунду, пока у неё хватает на это маны.
Волшебница хочет спасти мир как можно быстрее, подскажите, сколько времени ей на это понадобится.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальное время в секундах, за которое Вика сможет победить всех чудовищ.
Примечание
В первом наборе входных данных Вика может после первой секунды потратить \(2\) единицы огненной маны, чтобы убить первое чудовище. После этого у неё останется \(2\) единицы водяной маны и \(1\) единица огненной. После третьей секунды в её распоряжении будет \(6\) единиц водяной маны и \(7\) огненной маны. Этого хватит, чтобы сразу убить второе и третьей чудовище.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 3
3
2 6 7
37 58
1
93
190 90
2
23 97
13 4
4
10 10 2 45
|
3
2
1
5
|