Pentru a sapa un sant de lungime S, apelam la o firma de constructii care ne pune la dispozitie muncitori de diverse categorii (in total C categorii notate 1, 2, ..., C). Un muncitor de categorie superioara munceste mai mult si mai bine, dar cere si un salariu mai mare. Vrem sa terminam lucrarea intr-o singura zi, asa ca ne intereseaza pentru fiecare categorie care e salariul si cati metri sapa pe zi un muncitor din categoria respectiva. In plus vrem sa angajam exact N muncitori (avem N locuri la masa!). Se mai stie ca pentru fiecare categorie exista un numar suficient de mare de muncitori si un muncitor nu se opreste pana nu sapa lungimea corespunzatoare categoriei sale.

Cerinta

Gasiti posibilitatea de a angaja N muncitori de diverse categorii care sa sape exact S metri intr-o zi si sa poata fi platiti cu suma cea mai mica posibila.

Date de intrare

Pe prima linie a fisierului de intrare sant.in sunt scrise numerele naturale S, N si C, (lungimea santului, numarul de muncitori pe care vrem sa-i angajam si numarul de categorii) separate prin cate un spatiu. Pe urmatoarele C linii sunt cate doua numere naturale L_i si P_i (i=1, 2, ..., C) reprezentand lungimea santului sapat si plata ceruta pentru o zi, de un muncitor de categoria i.

Date de iesire

Prima linie a fisierului sant.out va contine suma minima care poate fi platita unui numar de N muncitori care sapa exact S metri intr-o zi sau cifra 0 daca nu exista solutie. Daca exista solutie, urmatoarea linie va contine un sir de N numere ordonate crescator, reprezentand categoriile muncitorilor angajati. Daca sunt mai multe solutii se va alege solutia cea mai mica din punct de vedere lexicografic (pentru cine a uitat, un exemplu: conform ordinei lexicografice sirul 1 1 1 2 3 3 este mai mic decat sirul 1 1 2 2 2 3).

Restrictii

• 1 <= S <= 100
• 1 <= N <= 50
• 1 <= C <= 10
• 1 <= L_i <= 50
• 1 <= P_i <= 100

Exemplu

prof. Mot Nistor
Colegiul National "N.Balcescu" - Braila
Contact:emotz_ro@yahoo.co.uk