Mini lokomotīves

Uzdevums

Vilciena sastāvu veido daudzi pasažieru vagoni un liela lokomotīve, kas šos vagonus velk. Lai nodrošinātos pret nepatikšanām, kas varētu rasties lielās lokomotīves salūšanas gadījumā, dzelzceļa vadība katrai stacijai ir nopirkusi pa trim minilokomotīvēm, kuras jāizmanto lielās lokomotīves salūšanas gadījumā. Minilokomotīve no lielās lokomotīves atšķiras ar to, ka var pavilkt tikai dažus vagonus.

Ir pieņemti stingri minilokomotīvju izmantošanas noteikumi:

1. Minilokomotīvei ir jānosaka maksimālais velkamo vagonu skaits (katrā stacijā šis skaitlis visām minilokomotīvēm ir vienāds) un neviena minilokomotīve nedrīkst vilkt vairāk par šo noteikto vagonu skaitu.
2. Izmantojot trīs minilokomotīves, pārvesto pasažieru skaitam jābūt pēc iespējas lielākam. Ir zināms, cik pasažieri ir katrā vagonā, pasažieru pāriešana starp vagoniem nav atļauta.
3. Katra minilokomotīve velk pēc kārtas sekojošus vagonus. Vagoni tiek numurēti ar naturāliem skaitļiem pēc kārtas. Vagonam, kurš atrodas aiz lielās lokomotīves, ir numurs 1.

Piemēram, ja pasažieru skaits vagonos ir tāds, kā redzams zīmējumā un katra minilokomotīve var pavilkt divus vagonus, tad maksimālais pārvesto cilvēku skaits ir 240 (pirmā minilokomotīve aizvelk pirmo un otro vagonu, otrā - trešo un ceturto vagonu, bet trešā - sesto un septīto vagonu).

Uzrakstiet programmu, kas nosaka kādu lielāko cilvēku skaitu var pārvest dotajam minilokomotīvju velkamo vagonu skaitam un pasažieru skaitam vagonos!

Ievaddati

Teksta faila miniloko.dat pirmajā rindā dots naturāls skaitlis N (N≤50000) - vagonu skaits sastāvā. Faila otrajā rindā doti N naturāli skaitļi. i-tais skaitlis šajā rindā (1≤i≤N) ir pasažieru skaits i-tajā vagonā. Neviena skaitļa vērtība šajā rindā nepārsniedz 100. Starp katriem diviem blakus skaitļiem ir viens tukšumsimbols. Faila trešajā rindā ir dots naturāls skaitlis M - lielākais minilokomotīves velkamo vagonu skaits. M vērtība nepārsniedz N/3.

Izvaddati

Teksta faila miniloko.rez vienīgajā rindā jāizvada lielākais pārvedamo pasažieru skaits.

Piemērs

miniloko.dat	miniloko.rez
7 35 40 50 10 30 45 60 2	240

Atsauces