Единственное отличие между простой и сложной версиями — точки, куда вы можете телепортироваться.
Рассмотрим точки \(0,1,\dots,n+1\) расположенные на прямой. Имеются телепорты, расположенные в каждой из точек \(1,2,\dots,n\). В точке \(i\) вы можете сделать следующее:
- Переместиться влево на единицу. Это стоит \(1\) монету.
- Переместиться вправо на единицу. Это стоит \(1\) монету.
- Воспользоваться телепортом в точке \(i\), если он существует. Это стоит \(a_i\) монет. В результате, вы телепортируетесь в точку \(0\) или \(n+1\) на ваш выбор. Каждым телепортом можно воспользоваться только один раз.
У вас есть \(c\) монет, и вы начинаете в точке \(0\). Каким наибольшим числом телепортов вы сможете воспользоваться?
Выходные данные
Для каждого набора входных данных выведите максимальное количество телепортов, которым вы сможете воспользоваться.
Примечание
В первом наборе входных данных вы можете переместиться на одну единицу вправо, использовать телепорт в точке \(1\) и телепортироваться в точку \(n+1\), переместиться на одну единицу влево и использовать телепорт в точке \(5\). У вас останется \(6-1-1-1-1 = 2\) монеты, этого недостаточно, чтобы использовать другой телепорт. Вы использовали два телепорта, поэтому ответ — два.
Во втором наборе входных данных вы перемещаетесь на четыре единицы вправо и используете телепорт, перемещаясь в \(n+1\), затем перемещаетесь на три единицы влево и используете телепорт в точке \(6\), перемещаясь в \(n+1\), и затем перемещаетесь влево на четыре единицы и используете телепорт. Общая стоимость составит \(4+6+3+4+4+9 = 30\) и вы использовали три телепорта.
В третьем наборе входных данных у вас недостаточно монет для использования любого телепорта, поэтому ответ равен нулю.
Примеры
| № | Входные данные | Выходные данные |
|
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
3
0
1
3
2
1
1
2
2
|