Вы сталкиваетесь с финальным боссом в своей любимой видеоигре. У босса \(h\) здоровья. У вашего персонажа есть \(n\) атак, \(i\)-я атака наносит \(a_i\) урона боссу, но имеет перезарядку \(c_i\) ходов, что означает, что вы сможете использовать эту атаку в следующий раз в ход \(x + c_i\), если ваш текущий ход \(x\). Каждый ход вы можете использовать сразу все атаки, которые сейчас не находятся в режиме перезарядки. Если все атаки находятся в режиме перезарядки, вы ничего не делаете в этот ход и переходите к следующему.
Изначально все атаки не находятся в режиме перезарядки. Сколько ходов вам понадобится, чтобы победить босса? Босс будет побежден, когда его здоровье станет \(0\) или меньше.
Выходные данные
Для каждого набора входных данных выведите целое число, минимальное количество ходов, необходимое для победы над боссом.
Примечание
В первом примере вы можете использовать атаки \(1\) и \(2\) на первом ходу, нанеся в общей сложности \(3\) урона и убив босса.
Во втором примере вы можете победить босса за \(3\) хода, используя следующие атаки:
Ход \(1\): Используйте атаки \(1\) и \(2\), нанеся \(3\) урона боссу. У босса осталось \(2\) здоровья.
Ход \(2\): Используйте атаку \(2\), нанеся \(1\) урон боссу. У босса осталось \(1\) здоровья.
Ход \(3\): Используйте атаку \(1\), нанеся \(2\) урона боссу. У босса осталось \(-1\) здоровья. Поскольку его здоровье меньше или равно \(0\), вы побеждаете босса.
В шестом примере: не забудьте использовать 64-битный целочисленный тип, так как ответ может быть большим.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
3 2
2 1
2 1
5 2
2 1
2 1
50 3
5 6 7
5 6 7
50 3
2 2 2
3 3 3
90000 2
200000 200000
1 1
100000 1
1
200000
6 7
3 2 3 2 3 1 2
6 5 9 5 10 7 7
21 6
1 1 1 1 1 1
5 5 8 10 7 6
|
1
3
15
25
1
19999800001
1
21
|