Masala #1173
Maksimal kuch yig'ish #EASY
Bu masalani yechish uchun siz quyidagi o'yin oxirida maksimal kuchga ega bo'lishingiz kerak. Xullas, o'yin quyidagicha:
Avvalo siz o'yinni X kuch bilan boshlaysiz. Keyinchalik esa sizda ketma-ket kelgan \(A_i\) kuchga ega bo'lgan raqiblarga to'qnash kelasiz. Agar u raqib sizdan kuchli bo'lsa siz hech narsa qila olmaysiz va agar unga hujum qilsangiz kuchingiz 0 ga tenglashadi. Lekin agar siz undan kuchli yoki kuchlaringiz teng bo'lsa siz unga hujum qilib mag'lub eta olasiz. Bu jang uchun sizning kuchingizga \(A_i\)(raqibning kuchi) qo'shiladi.
Eslatma: Siz raqib bilan jang qilishingiz yoki qilmasligingiz mumkin. Agar siz jang qilmasangiz, keyingi raqib tomonga yo'l olasiz. Lekin siz hech qachon oldin sizga uchragan raqib bilan qayta uchrasha olmaysiz!
Birinchi qatorda testlar soni - t(1≤t≤100) kiritiladi.
Har bir test-case ichi quyidagicha bo'ladi:
1 - qatorda raqiblar soni n(1≤n≤10\(^5\)) va x (\(1<=x<=10^9\))
Keyingi qatorda n ta son raqiblar kuchlari(1≤A≤\(10^9\)).
Yagona qatorda maksimal kuchni chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
1 4 3 2 6 5 8 |
18 |
Boshida bizda X = 3 bo'ladi va biz 2 darajaga ega bo'lgan raqibni yenga olamiz. Bundan keyin, X = 5. 6 darajadagi raqibni yenga olmaymiz chunki 6>5. A = 5 bo'lgan raqibni yengamiz va X = 5+5 = 10. A = 8 ni ham yengib bo'lganimizdan keyin X = 10+8=18 bo'ladi.
Telegram kanalimizga obuna bo'ling