Rezolvare PBinfo #1592

Eroul nostru, Costy merge la magazin pentru a-şi cumpăra biscuiţi. Vânzătorul îi spune că biscuţii costă S nasturi, şi că doreste ca plata lor să fie făcută cu n tipuri diferite de nasturi. De asemenea, vânzătorul precizează că ar dori ca numărul de nasturi din fiecare tip i să depăşească valoarea x[i], dar, să nu depăşească valoarea y[i]. Presupunând că baiatul are o infinitate de nasturi din fiecare tip şi că doreşte să rămână cu cât mai mulţi nasturi de tipurile n, n-1, n-2,.. în buzunar, ajutaţi-l să efectueze plata şi să pună cât mai repede mâna pe biscuiţi.

Cerința

Scrieţi un program care să determine o modalitate de plată a sumei, respectând condiţiile din enunţ.

Date de intrare

Fişierul de intrare plata.in conţine: Pe prima linie, N S, reprezentând numărul de tipuri de nasturi şi suma care trebuie platită. Pe următoarele N linii, două numere separate printr-un spaţiu, x[i] y[i], reprezentând numărul minim şi numărul maxim de nasturi de tipul i, care pot fi aleşi.

Date de ieșire

Fişierul de ieşire plata.out va conţine o linie cu n numere, separate prin câte un spatiu, r[1] r[2] r[3] . . . r[n] reprezentând numărul de nasturi de tipul i ales, sau cuvântul « imposibil » (fără ghilimele) dacă plata nu se poate realiza în condiţiile date.

Restricții și precizări

• 1 ≤ n ≤ 1000
• 1 ≤ x ≤ y ≤ 1000
• 1 ≤ s ≤ 1.000.000
• Nasturii au aceeaşi valoare, indiferent de tipul acestora.

Exemplu:

plata.in

5 18
1 2
4 6
1 4
5 8
1 3

plata.out

2 6 4 5 1

Explicație

Eroul nostru va face plata in felul următor:
2 nasturi de tipul 1, 6 nasturi de tipul 2 , 4 nasturi de tipul 3, 5 nasturi de tipul 4, 1 nasture de tipul 5,
În total 2 + 6 + 4 + 5 + 1 = 18 nasturi
De observat că dacă se alegea soluţia : 1 6 4 6 1, aceasta nu era corectă deoarece Costy trebuia să scoată din buzunar un nasture de tip mai mare în schimbul celui de tip 1.