Farmer John a une balance à vaches et $N$ ($1 \le N \le 1000$) poids connus (tiennent dans 31 bits) sur un plateau. Vache d'un côté, poids de l'autre jusqu'à équilibre. Pas ensemble : elle les lui donne au visage à coups de sabot dès que possible. Au-delà de $C$ ($1 \le C < 2^{30}$) sur un côté, la balance casse.

Triés du plus petit au plus grand, dès le troisième chaque poids vaut au moins la somme des deux précédents.

Il veut la masse maximale exactement mesurable, somme au plus $C$, donc pas forcément tous les poids.

Écrivez un programme du listing et de la capacité trouvant la masse légale maximale exactement mesurable.

Entrée

Ligne 1 : entiers positifs $N$, $C$ séparés par un espace.

Lignes $2..N+1$ : un entier positif de masse chacun, ordre non décroissant garanti.

Sortie

Ligne 1 : entier, masse maximale mesurable précisément et sans danger.

Exemples

Entrée 1

3 15
1
10
20

Sortie 1

11

Remarque

Trois poids 1,10,20, plateau limite 15.

1 et 10 mesurent 11. Toute masse supérieure réalisable casse la balance.