BANKA

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각 사람이 P_i분씩 걸리는 일을 마감 시각 T_i 안에 끝내도록 순서를 정할 때, 일을 끝낼 수 있는 사람 수의 최댓값을 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 정렬, 힙, 구간
정답자: 아직 제출이 없습니다

문제

Mirko radi za šalterom u banci. Jednoga dana dogodila se njegova najgora noćna mora! $N$ ljudi se istodobno pojavilo na ulazu u banku. Sada Mirko ne zna kojim ih redom primiti!

Mirko dobro poznaje svoje klijente. Za svaku osobu zna da može maksimalno provesti $T\_i$ minuta u banci i da posao koji treba obaviti traje $P\_i$ minuta.

Na primjer, imamo dvije osobe, jedna može biti maksimalno pet minuta u banci i trebaju joj tri minute da obavi svoj posao, dok druga može biti maksimalno šest minuta u banci i trebaju joj četiri minute da obavi svoj posao. Ako Mirko prvo primi prvu osobu i s njom provede tri minute neće moći primiti drugu jer bi ona svoj posao završila u sedmoj minuti, a u banci može biti maksimalno šest minuta.

Mirka zanima koliko maksimalno ljudi može stići obaviti svoj posao. Budući da nije vješt u organizaciji, traži od tebe pomoć! Pomozi mu odgovoriti na ovo pitanje.

입력

U prvom je retku prirodan broj $N$ ( $1 ≤ N ≤ 200\\,000$ ), broj iz teksta zadatka.

U $i$ -tom od sljedećih $N$ redaka nalaze se dva prirodna broja $T\_i$ i $P\_i$ ( $1 ≤ P\_i ≤ T\_i ≤ 200\\,000$ ) – maksimalno vrijeme koje $i$ -ta osoba može provesti u banci i koliko vremena treba za obaviti posao.

출력

U prvi i jedini redak ispiši koliko maksimalno osoba može obaviti svoj posao u banci.

힌트

Opis prvog probnog primjera: Mirko će u prve četiri minute obaviti posao s četvrtom osobom, iduće tri će obaviti posao s trećom osobom. Sada je prošlo ukupno sedam minuta, te prva i druga osoba više svoje poslove ne stignu obaviti. U idućoj minuti Mirko obavlja posao s petom osobom. Dakle tri osobe su uspjele obaviti svoje poslove.

예제3

예제 1
입력
```
5
10 4
10 5
7 3
4 4
12 1
```
예상 출력
```
3
```
예제 2
입력
```
6
11 3
11 1
11 3
11 5
11 3
11 3
```
예상 출력
```
4
```
예제 3
입력
```
3
2 1
1 1
2 1
```
예상 출력
```
2
```