ŽUPANIJSKO NATJECANJE 2013. / Srednja škola, I. podskupina (1. i 2. razred) - 3. zadatak

Luka radi u tvornici čokolade, gdje je upravo dobio zadatak sastaviti zadani broj poklon paketa.

Jedan poklon paket se sastoji od čokolada raznih veličina, težina i oblika zapakiranih u jednu kutiju.

Svaka kutija ima odreĎeni kapacitet K, a svaka čokolada ima određeni broj kalorija X.

Stroga pravila Agencije za istraživanje ruda i gubljenje vremena pri nadležnom ministarstvu nalažu da se određeni skup čokolada može zapakirati u kutiju samo ako je trostruka vrijednost zbroja kalorija čokolada u skupu, uvećana za kvadrat maksimalne vrijednosti kalorija u skupu i umanjena za kvadrat minimalne vrijednosti kalorija u skupu manja ili jednaka od kapaciteta kutije.

Drugim riječima, čokolade s brojem kalorija X1, X2,..., XM se mogu zapakirati u jedan poklon paket ako i samo ako je kapacitet kutije K takav da vrijedi:

Luka radi na pokretnoj traci kojom dolaze čokolade te ih mora pakirati redom u trenutnu kutiju koju u nekom trenutku zatvara i donosi novu kutiju koju nastavlja pakirati.

Dakle, u svaku kutiju mora zapakirati niz uzastopnih čokolada s pokretne trake.

Luka unaprijed zna broj kalorija za svaku čokoladu koja se nalazi na pokretnoj traci i trenutno mora naručiti hrpu kutija za pakiranje koje sve moraju biti istog kapaciteta.

Cilj mu je naručiti kutije što manjeg kapaciteta, a da opet može napraviti točno P poklon paketa i iskoristiti svih N čokolada na pokretnoj traci.

Napišite program koji za zadani niz od N čokolada i traženi broj paketa P manji ili jednak od N, pronaći najmanji mogući kapacitet K tako da je moguće zadani traženi niz čokolada zapakirati u točno P paketa kapaciteta K na opisani način.

Primijetite da je rješenje uvijek moguće – budući da P nije veći od N, Luka uvijek može zatražiti pakete jako velikog kapaciteta i lagano obaviti posao.

Ulazni podaci

U prvom retku ulaza nalaze se prirodni brojevi N i P (1 ≤ P ≤ N ≤ 100 000), broj čokolada na pokretnoj traci i broj paketa koje je potrebno sastaviti.

U drugom retku ulaza nalazi se N brojeva Xi (1 ≤ Xi ≤ 1000) odvojenih s po jednim razmakom koji označavaju broj kalorija odgovarajuće čokolade.

Čokolade su dane onim redom kojim se nalaze na pokretnoj traci i kojim ih Luka mora pakirati.

Izlazni podaci

U prvi i jedini redak izlaza potrebno je ispisati prirodan broj K, traženi najmanji kapacitet kutija kako je opisano u tekstu zadatka.

Primjeri test podataka

Ulaz

8 3
1 4 5 6 3 2 5 3

Izlaz

54

Objašnjenje

Pojašnjenje prvog test primjera: Ako u prvi paket stavimo prve tri čokolade, potrebna je kutija kapaciteta 3*(1+4+5) + 52- 1^2 = 54.

Sljedeće dvije čokolade zahtijevaju kapacitet kutije od

3**(6+3) + 62 - 3^2 = 54, dok je za posljednje tri čokolade potreban kapacitet 3(2+5+3)+52 -2^2 = 51.

Ulaz

5 4
3 3 3 6 6

Izlaz

18