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 <= 1000000
• 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.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("plata.in");
ofstream cout("plata.out");

int x[1001], y[1001];
int sp[1002];

int main()
{
    int n, s;
    cin >> n >> s;
    int smax = 0;
    int smin = 0;
    for(int i = 1 ; i <= n; ++i)
        cin >> x[i] >> y[i], smax += y[i], smin += x[i];
    for(int i = n; i >= 1; --i)
        sp[i] = sp[i+1] + x[i];
    int sum = 0;
    if(smax >= s && smin <= s)
    for(int i = 1 ; i <= n; ++i)
    {
        sum += y[i];
        if(sum + sp[i + 1] >= s)
        {
            if(sum + sp[i+1] == s)
            {
                cout << y[i] << ' ';
                for(int j = i + 1; j <= n; ++j)
                    cout << x[j] << ' ';
                i = n;
            }
            else
            {
                cout << y[i] + s - sum - sp[i + 1] << ' ';
                for(int j = i + 1; j <= n; ++j)
                    cout << x[j] << ' ';
                i = n;
            }

        }
        else
            cout << y[i] << ' ';
    }
    else
        cout << "imposibil";
    return 0;
}