Shop

shop

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

Zaharel face din nou cumparaturi in magazinul detinut de Nargy si Fumeanu. Dupa ce a cumparat produse in valoarea de $L$ lei, Zaharel trebuie sa plateasca fix $L$ lei la casa folosind monezile pe care le are. Se stie ca in tara lui Zaharel toate monezile sunt de forma $C^P^$ unde $C$ este o valoare fixata de guvern. Astfel, Zaharel are la dispozitie $N$ tipuri de monezi, moneda de tipul $i$ avand valorand $C^A{~i~}^$ lei, iar Zaharel detine $B{~i~}$ astfel de monezi. Desigur, Zaharel doreste sa plateasca suma de $L$ lei cu numar minim de monezi.

Poveste si cerinta...

h2. Date de intrare

Fisierul de intrare $shop.in$ contine pe prima linie numerele naturale $N, C, L$ separate prin spatii. Urmatoarele $N$ linii contin perechi de numere $A{~i~} B{~i~}$ cu semnificatia prezentata mai sus.

...

h2. Date de iesire

In fisierul de isire $shop.out$ se va scrie un singur numar natural, reprezentand numarul minim de monezi necesare pentru a plati suma de $L$ lei. Urmatoarea linie va contine $N$ numere naturale, al $i$-lea numar reprezentand de cate ori s-a folosit moneda de tip $i$.

...

h2. Restrictii

* $1 ≤ N ≤ 30$
* $1 ≤ C ≤ 10$
* $0 ≤ L ≤ 10^16^$
* $0 ≤ A{~i~} ≤ 32$
* $1 ≤ B{~i~} ≤ 10^9^$
* Se garanteaza ca valoarea oricarei monezi este mai mica sau egala cu $L$
* Cele $N$ tipuri de monezi sunt distincte ca valori
* Pentru $50%$ din teste $L ≤ 1.000.000$
* Se garanteaza existenta unei solutii; daca exista mai multe solutii se poate afisa oricare

* $... ≤ ... ≤ ...$

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

|4 2 47
0 5
3 2
2 4
4 1
| 9
3 2 3 1 |

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

h3. Explicatie

$47 = 2^0^ + 2^0^ + 2^0^ + 2^3^ + 2^3^ + 2^2^ + 2^2^ + 2^2^ + 2^4^ = 1 + 1 + 1 + 8 + 8 + 4 + 4 + 4 + 16$

...

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

1753