Masala #1029

Xotira 64 MB Vaqt 1000 ms
14

Crazy monster game #2

Azimjon crazy monster game o'yinini o'ynashni yoqtiradi. Ushbu o'ynda \(n\) ta monster ga qarshi jang olib borish kerak bo'ladi(monsterlar bitta chiziqda joylashgan).

Azimjon monsterlar ustidan g'alaba qozonishi uchun dastlab har bir monsterning umumiy kuchini aniqlab olishi kerak.  \(i-\)monsterning kuchi \(s_i\) ga teng, umumiy kuchi esa \(i-\)monsterdan ko'pi bilan \(r\) masofadagi monsterlar kuchlari yig'indisiga teng.

Har bir monsterni umumiy kuchini aniqlab bo'lgach Azimjon jang qilishga hozirlanadi va Azimjonning dastlabki kuchi \(h\) ga teng. Agar  \(i-\)monsterning umumiy kuchidan Azimjonning kuchi kam bo'lmasa \(i-\)monster ustidan g'alaba qozonadi(Azimjon istalgan monster bilan jangga kirishi mumkun deb qaralsin va u bir vaqtda bir nechta monsterlar bilan jang qilmaydi) va \(s_i\) bonusga ega bo'ladi, uning kuchi \(h=h+s_i\) ga ortadi. Aks holda mag'lubiyatga uchraydi.

Bu o'yinda Azimjon g'alaba qozonadimi buni aniqlashda unga yordam bering.


Kiruvchi ma'lumotlar:

Kirish faylining dastlabkis satrida \(n, r, h(1\leq n\leq 10^6, 0\leq r\leq n,0\leq h\leq 10^9)\) butun sonlar. Kiyingi satrda \(n\) son \(s_i(1\leq s_i\leq 10^9)\) monsterlar kuchlari beriladi.


Chiquvchi ma'lumotlar:

Agar o'yinda Azimjon g'alaba qozonsa "Next level" so'zini va jami to'plagan achkosini bitta satrda probil bilan ajratilgan holda chop eting. Aks holda "Game over" so'zini chop eting.


Misollar
# input.txt output.txt
1
3 1 99
1 0 100
Next level 200
2
3 1 99
1 1 100
Game over
Izoh:

Birinchi testda monsterlar kuchlari \([1,0,100]\) ga teng bo'lsa umumiy kuchlari \([1,101,100]\) ga teng. Azimjon dastlab birinchi monster bilan janga kiradi\((1\leq99)\) va uni mag'lubiyatga uchratib 1 bonsuga ega bo'ladi \(99+1\). Endi u uchinchi monster bilan jang qiladi\((100\leq100)\) va 100 bonusga ega bo'ladi \(100+100\). Nihoyat oxirgi monsterni mag'lubiyatga \((101\leq200)\) uchratadi \(200+0\). Jami bonuslari \(200\).

Ikkinchi testda monsterlar kuchlari \([1,1,100]\) ga teng bo'lsa umumiy kuchlari \([2,102,101]\) ga teng. Azimjon birinchi monster bilan jang qiladi\((2\leq 99)\) va uni mag'lubiyatga uchratib 1 bonusga ega bp'ladi \(99+1\). Endi uning kuchi \(100\) ga teng ammo qolgan ikki monster umumiy kuchlaridan kichik bo'lganligi uchun o'yinda mag'lubiyatga uchraydi.