U potrazi za blagom našli ste se u mračnom napuštenom hodniku negdje duboko ispod površine Osijeka. Pred vama je niz od \(n\) zaključanih vrata čije brave zahtijevaju posebne ključeve. U hodniku susrećete čarobnjaka Tomu koji je smislio jednu igru za vas.

Da biste otključali jedna vrata morate kupiti ključ od čarobnjaka Tome koji košta točno \(k\) zlatnika. Iza svakih vrata nalazi se hrpa od \(a_i\) zlatnika koje uzimate nakon što otključate ta vrata. No, čarobnjak Tomo nudi vam još jednu mogućnost: možete iskoristiti besplatni čarobni ključ koji će otključati jedna vrata, ali količina zlatnika iza svih neotvorenih vrata (uključujući i vrata koja ćete upravo otvoriti) će se cjelobrojno prepoloviti. Dakle, količina zlatnika iza nekih i-tih vrata postat će \(\lfloor \frac{a_i}{2}\rfloor\).

Čarobnjak vam je zadao još jedno posebno pravilo: vrata morate otvarati redom, od vrata \(1\) do vrata \(n\). Čarobnjak se također osjećao velikodušno pa će dozvoliti da vaš saldo ode u minus, što znači da ako imate \(2\) zlatnika i kupite ključ za \(3\) zlatnika imati ćete \(-1\) zlatnik.

Vaš je zadatak nadmudriti čarobnjaka Tomu i imati što više zlatnika nakon otvaranja svih vrata redom.

Ulazni podatci

U prvome retku nalaze se cijeli brojevi \(n\) (\(1 \leq n \leq 10^5\)) i \(k\) (\(0 \leq k \leq 10^9\)), brojevi iz zadatka.

U drume retku nalazi se \(n\) brojeva \(a_i\) (\(0 \leq a_i \leq 10^9\)), broj zlatnika iza i-tih vrata.

Izlazni podatci

U prvi i jedini redak ispišite maksimalan broj zlatnika koje možete imati nakon otvaranja svih vrata redom.

Podzadatci

Ulaz primjera 1

4 6
11 13 3 7

Izlaz primjera 1

14

Pojašnjenje primjera 1

Za vrata \(1\) kupimo ključ koji košta \(6\) zlatnika: \(0 - 6 + 11 = 5\)
Za vrata \(2\) kupimo ključ: \(5 - 6 + 13 = 12\)
Za vrata \(3\) iskoristimo čarobni ključ: \(12 + \lfloor \frac{3}{2}\rfloor = 12 + 1 = 13\), a vrata \(4\) sada sadrže \(3\) zlatnika
Za vrata \(4\) iskoristimo čarobni ključ: \(13 + \lfloor \frac{3}{2}\rfloor = 14\)

Ulaz primjera 2

1 17
18

Izlaz primjera 2

9

Ulaz primjera 3

6 9
7 3 27 44 9 30

Izlaz primjera 3

66