Жирная крыса и её друг Сerealguy поспорили — спустится ли к ним по хитроумной конструкции хоть чуть-чуть хлопьев. На рисунке ниже показана хитроумная конструкция.

Более формальное описание хитроумной конструкции следует далее. Хитроумная конструкция состоит из n рядов с весами. В первом ряду n весов, во втором (n - 1) весов, в i-ом ряду (n - i + 1) весов, в последнем ряду ровно одни весы. Пронумеруем весы в каждом ряду слева направо, начиная с 1. Тогда величина w_i, k в килограммах (1 ≤ i ≤ n; 1 ≤ k ≤ n - i + 1) обозначает параметр выдержки k-х весов в i-ом ряду.

Если на весы с параметром выдержки w_i, k падает тело с массой не меньшей чем w_i, k, то весы ломаются. При этом все, что было на весах, падает либо на уровень ниже влево (если это возможно), либо на уровень ниже вправо (если это возможно). Другими словами, если ломаются весы w_i, k (i < n), то возможно максимум два варианта падения содержимого весов: все содержимое весов w_i, k падает либо на весы w_{i + 1, k - 1} (если такие существуют), либо на весы w_{i + 1, k} (если такие существуют). Если ломаются весы w_n, 1, то все содержимое этих весов падает прямо в руки жирной крысе. Обратите внимание, что у первых в ряду весов и у последних в ряду весов существует ровно один вариант падения содержимого.

Изначально, на все весы первого уровня одновременно кладутся хлопья. На i-е весы кладется a_i килограмм хлопьев. После этого весы начинают ломаться, а хлопья начинают падать вниз каким-то образом. Можно считать, что все происходит мгновенно. То есть весы ломаются мгновенно и хлопья падают тоже мгновенно.

Жирная крыса утверждает, что ни при каком развитии событий хлопья с первого уровня не смогут попасть к ней в руки. Cerealguy утверждает, что существует такое развитие событий, при котором в руки крысе попадет хоть сколько-нибудь хлопьев. Помогите жирной крысе и Cerealguy. Определите, кто их них прав.