Вы играете в игру под названием Слаймовый побег. Игра проходит на числовой прямой. Изначально на прямой \(n\) слаймов. Для каждого целого числа \(i\) такого, что \(1 \le i \le n\), \(i\)-й слайм находится в позиции \(i\) и имеет здоровье \(a_i\). Вы управляете слаймом в позиции \(k\).
С прямой два выхода в позициях \(0\) и \(n+1\). Ваша цель — достигнуть любого из двух выходов после выполнения любого количества шагов.
За один шаг вы можете переместить свой слайм налево или направо на одну позицию. Однако если в позиции, куда вы перемещаете свой слайм, есть другой слайм, вы должны его поглотить. При поглощении слайма к здоровью вашего слайма добавляется здоровье поглощенного слайма, а после этого поглощенный слайм убирается из игры.
Обратите внимание, что у некоторых слаймов может быть отрицательное здоровье, и ваше здоровье уменьшится при поглощении таких слаймов.
Вы проигрываете, если в какой-то момент игры здоровье вашего слайма становится отрицательным.
Можете ли вы достичь одного из двух выходов, не проиграв?
Выходные данные
Для каждого набора входных данных выведите «YES» (без кавычек), если можно добраться до выхода, не проиграв, иначе выведите «NO» (без кавычек).
Примечание
В первом примере вы управляете слаймом в позиции \(4\) со здоровьем \(6\). Один из способов выбраться — поглотить слаймов в позициях \(5\), \(6\) и \(7\). Вы достигнете выхода со здоровьем \(0\) в позиции \(8\).
Во втором примере вы управляете слаймом со здоровьем \(232\) в позиции \(1\). Так как ваш слайм уже у выхода в позиции \(0\), вы можете сразу переместиться туда, не поглощая других слаймов.
В третьем примере можно показать, что здоровье вашего слайма всегда достигнет отрицательных значений до того, как вы достигнете выхода.
В четвертом примере вы управляете слаймом в позиции \(4\) со здоровьем \(6\). Ниже описана возможная последовательность действий для победы.
- Поглотить слаймов в позициях \(5\), \(6\) и \(7\): ваше здоровье становится равно \(4\) после поглощения слайма со здоровьем \(-2\); становится \(1\) после поглощения слайма со здоровьем \(-3\); \(7\) после поглощения слайма со здоровьем \(6\).
- Поглотить слаймов в позициях \(3\) и \(2\): ваше здоровье становится \(7-7+10=10\).
- Поглотить слайм в позиции \(8\): ваше здоровье становится \(10-10=0\).
- Дойти до выхода в позиции \(9\).
Так как здоровье вашего слайма всегда оставалось неотрицательным, вы выиграли.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
7 4
-1 -2 -3 6 -2 -3 -1
3 1
232 -500 -700
7 4
-1 -2 -4 6 -2 -4 -1
8 4
-100 10 -7 6 -2 -3 6 -10
8 2
-999 0 -2 3 4 5 6 7
7 3
7 3 3 4 2 1 1
|
YES
YES
NO
YES
NO
YES
|