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 exact cele $P$ conserve cumparate, celor $N$ participanti si totodata sa obtina o cantita maxima.

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.

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 nr 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 numar natural reprezentand greutatea conservei $i$.

h2. Date de iesire

h2. Restrictii

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

* $3$ ≤ $N$, $P$ ≤ $4.096$

* 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 |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|  6 7
   178
   25
   123
   34
   56
   79
   100
|  570
   6
   1 3 4 5 6 7

|

h3. Explicatie
 
...
 

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

1861