Однажды Ахмед Хоссам пришел к Хемосе и сказал: «Давай порешаем контест с тренировок!». Хемосе не хотел этого делать, так как он играл в Valorant, поэтому он придумал задачу и рассказал ее Ахмеду, чтобы отвлечь его. К сожалению, Ахмед не может ее решить... Не могли бы вы ему помочь?
В игре Valorant есть Агент, и у него есть \(n\) оружий. \(i\)-е оружие имеет значение урона \(a_i\), и Агент столкнется с врагом, чье здоровье равно \(H\).
Агент будет делать один или больше ходов, пока враг не умрет.
За один ход Агент выбирает оружие и уменьшает здоровье врага на величину урона этого оружия. Враг умрет, когда его здоровье станет меньше или равно \(0\). Однако не все так просто: Агент не может использовать одно и то же оружие \(2\) раза подряд.
Какое минимальное количество раз Агенту нужно использовать оружие, чтобы убить врага?
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество раз, которое Агент должен будет использовать оружие, чтобы убить врага.
Примечание
В первом наборе входных данных Агент может использовать второе оружие, в результате чего здоровье врага становится равным \(4-7=-3\). \(-3 \le 0\), поэтому враг мертв, и использования оружия \(1\) раз было достаточно.
Во втором наборе входных данных Агент может использовать сначала первое оружие, а затем второе. После этого здоровье врага упадет до \(6-4-2 = 0\), то есть он будет убит после использования оружия \(2\) раза.
В третьем наборе входных данных Агент может использовать оружия в порядке (третье, первое, третье), уменьшая значение здоровья врага до \(11 - 7 - 2 - 7 = -5\) после использования оружия \(3\) раза. Обратите внимание, что мы не можем убить врага, используя третье оружие дважды, поскольку даже хотя \(11-7-7<0\), одно и то же оружие не разрешается использовать дважды подряд.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 4
3 7
2 6
4 2
3 11
2 1 7
|
1
2
3
|