Farmer John ha bilancia per mucche e $N$ ($1 \le N \le 1000$) pesi noti (31 bit) su un lato. Mucca in uno, pesi altro fino equilibrio. Non insieme, li calcia al suo viso appena può. Sopra $C$ ($1 \le C < 2^{30}$) su un lato rompe.

Dal piccolo al grande ogni peso dal terzo vale almeno somma dei due precedenti.

Vuole massima massa esatta, totale al massimo $C$, forse non tutti pesi.

Da lista e capacità trova massima massa legale misurabile esattamente.

Input

Riga 1: positivi interi $N$, $C$ con spazio.

Righe $2..N+1$: massa intera positiva ciascuna, ordine non decrescente garantito.

Output

Riga 1: intero, massima massa precisa e sicura.

Esempi

Input 1

3 15
1
10
20

Output 1

11

Spiegazione

Tre pesi 1,10,20, limite lato 15.

1 e 10 misurano 11. Qualsiasi massa maggiore formabile rompe bilancia.