Cerința

Pentru cadourile pe care Moş Crăciun urmează să le cumpere copiilor cuminţi, Consiliul Polului Nord a alocat suma de S eureni. Ştiind că în comerţul polar se utilizează n+1 tipuri de bancnote de valori 1, e1, e2, e3,…, en şi faptul că Moşul trebuie să primească un număr minim de bancnote pentru suma aprobată, să se determine numărul de bancnote din fiecare tip utilizat în plata sumei şi numărul total de bancnote care i s-au alocat.

Date de intrare

Fișierul de intrare eureni.in conține pe prima linie numerele naturale S n e.

Date de ieșire

Fișierul de ieșire eureni.out va conține mai multe linii: pe fiecare linie va fi scrisă valoare unei bancnote folosită în plata sumei S și numărul de bancnote folosite, separate printr-un spațiu, în ordinea descrescătoare a valorilor bancnotelor folosite. Pe ultima linie se va scrie numai numărul total de bancnote folosite.

Restricții și precizări

• 1 < S < 2 000 000 000
• 1 < n < 10
• 1 < e < 10
• se presupune că există un număr nelimitat de bancnote de fiecare tip

Exemplu:

eureni.in

107 4 5

eureni.out

25 4
5 1
1 2
7

Explicație

Sunt 5 tipuri de bancnote, cu valorile: 1, 5, 25, 125, 625 eureni. Pentru a plăti suma de 107 eureni se folosesc 4 bancnote de 25 eureni, 1 bancnotă de 5 eureni și 2 bancnote de 1 euren, în total 7 bancnote.