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

Pe prima linie se va afla suma maxima ceruta. Pe linia a doua numarul de conserve necesare formarii acestei sume, iar pe linia a treia conservele folosite.

...

h2. Restrictii

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

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

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

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

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

|

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

h3. Explicatie
 
...
== include(page="template/taskfooter" task_id="conserve") ==

1861