Nosaukums
Mini lokomotīves (miniloko)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
55%

Definīcija

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!


Ievaddatu raksturojums

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.


Izvaddatu raksturojums

Vienīgajā rindā jāizvada lielākais pārvedamo pasažieru skaits.


Piezīmes

Uzdevums izmantots Korejas informātikas olimpiādē 2003.gadā


Paraugdati

Stdin
7
35 40 50 10 30 45 60
2
Stdout
240

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.