Tremenda vergonya P76203


Statement
 

pdf   zip

thehtml

Per celebrar la desena classificació per a les finals mundials, els equips de programació de la UPC van decidir organitzar una performance sorpresa al Roura (el seu entrenador) enmig d’un examen final d’Algorísmia.

Aquesta actuació va ser molt improvisada, i la majoria de les parts van fer passar vergonya a tothom. Després d’una anàlisi exhaustiva, els organitzadors van aconseguir descriure cada part i amb dos paràmetres: la quantitat intrínseca de cringe ci, i la vergonya vi que va passar el Roura durant aquella part.

Es volen penjar parts de la performance al YouTube per tal de maximitzar la vergonya del Roura, però sense que el cringe total passi d’un cert límit C. Sabríeu fer-ho?

 ‍ ‍ ‍ (Part on ci i vi van ser bastant alts.)

Entrada

L’entrada consisteix en diversos casos, només amb nombres enters, amb el nombre de parts ‍n i C (ambdós entre 1 i 1000), seguits dels n parells ci vi, tots entre 1 i 109.

Sortida

Per a cada cas, escriviu la màxima suma possible de les vi, però amb la condició que la suma de les ci corresponents no passi de C.

Public test cases

  • Input

    3 1000  400 10000  601 25000  500 20000
2 20  21 1000000000  1000000000 1
4 42  14 1000000000  20 1000000000  4 1000000000  4 1000000000

    Output

    30000
0
4000000000
    • Information
    Author
    Ivan Geffner
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++