Правительство Берляндии наконец-то решило улучшить покрытие сетью Интернет в своей стране. Берляндия имеет уникальную структуру: в самом центре находится столица, а \(n\) городов расположены вокруг нее по кругу. В столице нет проблем с Интернетом (поэтому правительство игнорирует ее), но в \(i\)-м городе необходимо провести соединение в \(a_i\) домов.
Правительство разработало план постройки \(n\) базовых станций между каждой парой соседних городов, которые будут обслуживать только эти города. Другими словами, \(i\)-я базовая станция будет обслуживать только \(i\)-й и \((i + 1)\)-й город (\(n\)-я станция будет обслуживать \(n\)-й и \(1\)-й город).
Все базовые станции имеют ограниченную мощность: к \(i\)-й станции может быть подключено не более \(b_i\) домов.
Сейчас же правительство просит вас проверить: могут ли спроектированные станции удовлетворить потребности всех городов или нет; то есть можно ли каждый дом подключить к базовой станции так, что к каждой станции \(i\) подключено не более \(b_i\) домов.
Выходные данные
Для каждого набора входных данных, выведите YES, если спроектированные станции смогут удовлетворить потребности всех городов, или NO в противном случае (регистр букв не важен).
Примечание
В первом наборе входных данных:
- первая базовая станция может предоставить \(2\) соединения первому городу и \(1\) соединение второму городу;
- вторая станция может предоставить \(2\) соединения второму городу и \(1\) соединение третьему городу;
- третья станция может предоставить \(3\) соединения третьему городу.
Во втором наборе:
- \(1\)-я станция может предоставить \(2\) соединения \(1\)-му городу;
- \(2\)-я станция может предоставить \(3\) соединения \(2\)-му городу;
- \(3\)-я станция может предоставить \(3\) соединения \(3\)-му городу и \(1\) соединение \(1\)-му городу.
В третьем примере, четвертому городу необходимо \(5\) соединений, но третья и четвертая станции могут предоставить только \(4\) соединения суммарно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
2 3 4
3 3 3
3
3 3 3
2 3 4
4
2 3 4 5
3 7 2 2
4
4 5 2 3
2 3 2 7
2
1 1
10 10
|
YES
YES
NO
YES
YES
|