Farmer John hat Kuhwaage und $N$ ($1 \le N \le 1000$) bekannte Gewichte (31 Bit) für eine Seite. Kuh auf einer, Gewichte auf anderer bis Gleichgewicht. Nicht gemeinsam: Kuh tritt sie bei Gelegenheit ins Gesicht. Mehr als $C$ ($1 \le C < 2^{30}$) auf einer Seite zerstört Waage.

Klein nach groß ist jedes ab drittem mindestens so schwer wie zwei vorige zusammen.

Er will größte exakt messbare Masse, Summe höchstens $C$, eventuell nicht alle Gewichte.

Bestimme aus Gewichten und Grenze die maximale zulässige exakt messbare Masse.

Eingabe

Zeile 1: positive ganze Zahlen $N$, $C$ mit Leerzeichen.

Zeilen $2..N+1$: jeweils positive ganze Masse, garantiert nicht fallend.

Ausgabe

Zeile 1: ganze Zahl, größte genaue sichere Masse.

Beispiele

Eingabe 1

3 15
1
10
20

Ausgabe 1

11

Hinweis

Drei Gewichte 1,10,20, Seitengrenze 15.

1 und 10 messen 11. Jede größere bildbare Masse zerstört Waage.