CSES - Tehtävät
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Sinun täytyy suorittaa nn tehtävää. Jokaiseen tehtävään liittyy kesto ja deadline. Voit suorittaa vain yhden tehtävän kerrallaan. Tehtävästä tuleva palkkio on dad-a, missä dd on deadline ja aa on tehtävän valmistumisaika.

Mikä on suurin mahdollinen yhteispalkkio, jonka voit saada?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku nn: tehtävien määrä.

Tämän jälkeen syötteessä on nn riviä, jotka kuvaavat tehtävät. Jokaisella rivillä on kaksi kokonaislukua kik_i ja did_i: tehtävän kesto ja deadline.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: suurin mahdollinen yhteispalkkio.

Rajat

  • 1n1051 \le n \le 10^5
  • 1ki1061 \le k_i \le 10^6
  • 1di1091 \le d_i \le 10^9

Esimerkki

Syöte:

3
6 10
8 15
5 12

Tuloste:

2