Masala #1174

Xotira 16 MB Vaqt 1000 ms
14

Maksimal kuch yig'ish #HARD

!Diqqat bu Maksimal kuch yig'ish masalasining qiyinroq versiyasi va sizning janglaringiz soni cheklangan.

 

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. Sizda k ta raqib bilan bellashish imkoniyati bo'ladi va siz ulardan foydalanishingiz yoki foydalanmasligingiz mumkin. 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:

1 - qatorda raqiblar soni n(1≤n≤25) va x (\(1<=x<=10^9\)) va k (1≤k≤\(20\))

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
4 3 2
2 6 5 8
10
Izoh:

Boshida bizda X = 3 bo'ladi va biz 2 kuchga ega bo'lgan raqibni yenga olamiz. Bundan keyin, X = 5. 6 kuchga ega raqibni yenga olmaymiz chunki 6>5. A = 5 bo'lgan raqibni yengamiz va X = 5+5 = 10. A = 8 ni ham yengib bo'lganimizda X = 10+8=18 bo'lar edi, ammo janglar soni cheklangan va javob  x= 10.