Tremenda vergonya P76203

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.

0.5 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 $c_i$, i la vergonya $v_i$ 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?

0.48 (Part on $c_i$ i $v_i$ 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 $c_i$ $v_i$, tots entre 1 i $10^9$.

Sortida

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