credite

Time limit: 0.1s Memory limit: 32MB Input: credite.in Output: credite.out

Maria este studentă în anul I la facultatea de informatică și a primit o listă de NN probleme, numerotate de la 11 la NN, pe care trebuie să le rezolve la cursul de algoritmică, rezolvarea unei probleme durând exact o unitate de timp. Pentru că profesorul vrea să testeze capacitatea elevilor de a a face cele mai bune alegeri, pentru fiecare problemă acesta a stabilit numărul de credite (CiC_i) pe care studentul le va primi dacă rezolvă problema ii, dar și un număr limită de unități de timp (TiT_i) până la care problema poate fi rezolvată.

Cerință

Cunoscând numărul de probleme, numărul de credite al fiecărei probleme precum și timpul limită de rezolvare al fiecărei probleme, scrieți un algoritm care determină numărul maxim de credite pe care le poate obține Maria.

Date de intrare

Pe prima linie a fișierului de intrare credite.in se găsește un număr natural NN, reprezentând numărul de probleme de pe listă.
Pe următoarele NN linii din fișierul de intrare vor fi datele despre fiecare problemă, pe linia i+1i+1 găsindu-se 22 numere naturale CiC_i și TiT_i care reprezintă numărul de credite, respectiv timpul limită pentru problema ii.

Date de ieșire

În fișierul credite.out se va afișa un singur număr natural, reprezentând numărul maxim de credite pe care Maria le poate obține.

Restricții și precizări

  • 2n10 0002 \leq n \leq 10 \ 000
  • 2Ci1 0002 \leq C_i \leq 1 \ 000
  • 1Ti10 0001 \leq T_i \leq 10 \ 000

Exemplu

credite.in

4
10 3
7 5
8 1
2 1

credite.out

25

Explicație

Maria alege să rezolve problema 33, renunțând la problema 44 pentru că are mai puține credite și același timp limită ca problema 33. După aceea va rezolva problemele 11 și 22, adunând în total 2525 de credite.

Log in or sign up to be able to send submissions!