Conserve

conserve

== include(page="template/taskheader" task_id="conserve") ==

Farfurel doreste sa organizeze o excursie la munte. Pentru excursie, el invita $N$ persoane. Stiind ca vor exista conflicte in ceea ce priveste transportul conservelor, Farfurel doreste sa imparta echitabil cele $P$ conserve cumparate celor $N$ participanti si totodata sa obtina o cantita maxima. Printr-o impartire echitabila se intelege selectarea unui subset de conserve astfel incat greutatea totala sa poata fi impartita celor $N$ participanti in mod egal si greutatea transportata de fiecare sa fie numar intreg.

Farfurel doreste sa organizeze o excursie la munte. Pentru excursie, el invita $N$ persoane. Stiind ca vor exista conflicte in ceea ce priveste transportul conservelor, Farfurel doreste sa imparta exact cele $P$ conserve cumparate, celor $N$ participanti si totodata sa obtina o cantita maxima.

h2. Date de intrare

Pe prima linie se gaseste $N$ si $P$, numarul de persoane invitate de Farfurel si numarul de conserve cumparate. Pe linia $i$, a urmatoarelor $P$ linii, se afla un numar natural reprezentand greutatea conservei $i$.

Pe prima linie se gaseste $N$ si $P$, numarul de persoane invitate de Farfurel si numarul de conserve cumparate. Pe linia i, a urmatoarelor P linii, se afla un nr natural reprezentand greutatea conservei i.

h2. Date de iesire

h2. Restrictii
* $3$ ≤ $N$, $P$ ≤ $4.096$

* Printr-o impartire exacta se intelege ca greutatea maxima sa poata fi impartita celor $N$ participanti.

* Daca exista mai multe solutii in ceea ce priveste alegerea conservelor, se va afisa oricare.
* Pentru afisarea sumei corecte se acorda $40$% din punctajul unui test.
* Greutatea unei conserve nu va depasi $500.000$.

h2. Exemplu
table(example). |_. conserve.in |_. conserve.out |

|  6 7
   178
   25

|  6 7
   178
   25

   123
   34
   56

|
== include(page="template/taskfooter" task_id="conserve") ==

1861