Šautriņas

Uzdevums

Jūs spēlējat šautriņu spēli pēc šādiem noteikumiem:

Katrā gājienā mērķī jāmet vismaz viena un ne vairāk kā četras šautriņas. Mērķis ir sadalīts N daļās, un trāpījums kādā no tām dod attiecīgi P₁, P₂, …, P _N punktus. Vairākas šautriņas var trāpīt vienā daļā. Saskaitot katra trāpījuma punktus, iegūst punktu summu S. Ja S nepārsniedz iepriekš zināmu skaitli M, tad jūs šajā gājienā saņemat S punktus. Savukārt, ja S pārsniedz M, tad jūs šajā gājienā saņemat 0 punktus.

Uzrakstiet programmu, kas aprēķina lielāko punktu skaitu, ko iespējams iegūt vienā gājienā!

Ievaddati

Teksta faila sautrina.dat pirmajā rindā dotas divu naturālu skaitļu N (N ≤ 1000) un M (M ≤ 200 000 000) vērtības, kas atdalītas ar vienu tukšumzīmi. Katrā no nākamajām N faila rindām dots viens naturāls skaitlis - punktu skaits, cik dod šautriņas trāpījums šajā daļā. Katram i (1 ≤ i ≤ N) faila (i+1)-ajā rindā ir dota P_i (P_i ≤ 10 ⁸) vērtība.

Izvaddati

Teksta faila sautrina.rez vienīgajā rindā jāizvada viens vesels nenegatīvs skaitlis - lielākā vienā gājienā iegūstamā punktu summa.

Piemērs

sautrina.dat	sautrina.rez
4 50 3 14 15 9	48	Trīs šautriņas 15 punktu daļā un viena – 3 punktu daļā.
sautrina.dat	sautrina.rez
3 21 16 11 2	20	Viena šautriņa 16 punktu daļā un divas – 2 punktu daļā.

Atsauces