Masala #1173

Xotira 20 MB Vaqt 1700 ms
14

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!


Kiruvchi ma'lumotlar:

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\)).


Chiquvchi ma'lumotlar:

Yagona qatorda maksimal kuchni chiqaring.


Misollar
# input.txt output.txt
1
1
4 3
2 6 5 8
18
Izoh:

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.