Единственное отличие между простой и сложной версиями — точки, куда вы можете телепортироваться.
Рассмотрим точки \(0, 1, \dots, n\) расположенные на прямой. Имеются телепорты, расположенные в каждой из точек \(1, 2, \dots, n\). В точке \(i\) вы можете сделать следующее:
- Переместиться влево на единицу. Это стоит \(1\) монету.
- Переместиться вправо на единицу. Это стоит \(1\) монету.
- Воспользоваться телепортом в точке \(i\), если он существует. Это стоит \(a_i\) монет. В результате, вы телепортируетесь в точку \(0\). Каждым телепортом можно воспользоваться только один раз.
У вас есть \(c\) монет, и вы начинаете в точке \(0\). Каким наибольшим числом телепортов вы сможете воспользоваться?
Выходные данные
Для каждого набора входных данных выведите максимальное количество телепортов, которым вы сможете воспользоваться.
Примечание
В первом наборе входных данных вы можете переместиться на одну единицу вправо, использовать телепорт в точке \(1\) и телепортироваться в точку \(0\), переместиться на две единицы вправо и использовать телепорт в точке \(2\). У вас останется \(6-1-1-2-1 = 1\) монета, этого недостаточно, чтобы использовать другой телепорт. Вы использовали два телепорта, поэтому ответ — два.
Во втором наборе входных данных вы перемещаетесь на четыре единицы вправо и используете телепорт, перемещаясь в \(0\), затем перемещаетесь на шесть единиц вправо и используете телепорт в точке \(6\), перемещаясь в \(0\). Общая стоимость составит \(4+6+6+4 = 20\). У вас осталось \(12\) монет, но этого недостаточно, чтобы добраться до любого другого телепорта и использовать его, поэтому ответ равен \(2\).
В третьем наборе входных данных у вас недостаточно монет для использования любого телепорта, поэтому ответ равен нулю.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
5 6
1 1 1 1 1
8 32
100 52 13 6 9 4 100 35
1 1
5
4 5
4 3 2 1
5 9
2 3 1 4 1
5 8
2 3 1 4 1
4 3
2 3 4 1
4 9
5 4 3 3
2 14
7 5
5 600000000
500000000 400000000 300000000 200000000 100000000
|
2
2
0
1
2
2
1
1
1
2
|