Placinte

Nimic nu se compară cu plăcintele calde ieșite din cuptorul bunicii! Alexa simte mirosul ispititor al bunătățurilor proaspete și coboară în bucătărie ca să descopere n tipuri diferite de plăcinte. Unele sunt cu mere, altele cu vișine, altele cu brânză, în fine! Bunica ei a făcut câte o infinitate din fiecare tip. Dacă fata alege să mănânce un tip de plăcintă, ea îl mănâncă numai sub forma unui set. Un set de plăcinte de tipul i este egal cu \( 2^{i-1} \). Fata cunoaște din experiență timpul \( T_i \) necesar pentru a mânca un set de plăcinte de tip i.

Cerința

Știind că fata va mânca fără preferințe câte seturi de plăcinte va vrea din fiecare tip, să se calculeze timpul minim necesar pentru a mânca cel puțin k plăcinte.

Date de intrare

Programul citește de la tastatură numerele n, k și apoi n numere, reprezentând timpurile \( T_1,T_2,…,T_n \) necesare pentru a mânca un set din fiecare tip de plăcintă (în ordine, tipurile 1, 2, …, n).

Date de ieșire

Programul va afișa pe ecran un singur număr, timplul minim necesar pentru a mânca cel puțin k plăcinte.

Restricții și precizări

• \( 1 \leq n \leq 30 \)
• \( 1 \leq k, T_i \leq 10^9 \)

Exemple

Intrare

4 11
2 3 4 5

Ieșire

9

În acest exemplu, este mai avantajos să mănânce un set de plăcinte de tip 4 (adică 8 plăcinte) și un set de tip 3 (4 plăcinte), consumând în total 12 plăcinte în 9 unități de timp. Ar putea să mănânce 11 plăcinte sub forma 1 + 2 + 8, dar ar dura 10 unități de timp.

…sau:

Intrare

2 5
1 3

Ieșire

5

…sau:

Intrare

5 1000000000
32145 1421431 13124 315125 124124

Ieșire

3281000000000