이번 학기에 앨리스는 $n$개의 과목을 수강했습니다. 이제 모든 기말고사를 마쳤으며, 앞으로 $n$일 동안 성적을 받게 됩니다.

$i$번째 날에 앨리스는 $i$번째 과목의 성적 $A_i$를 알게 됩니다. 만약 $A_i$가 첫 $i-1$개 과목의 평균 성적보다 엄격하게 작다면, 앨리스는 그날 슬퍼하게 됩니다.

밥은 대학교 데이터베이스를 해킹하고 있습니다. 밥은 과목의 집합 $S$를 선택할 수 있습니다($S$는 공집합일 수 있습니다). 그리고 $S$에 속한 각 과목 $i$에 대해, 앨리스의 성적을 $A_i$에서 $B_i$로 변경할 수 있습니다.

밥은 앨리스가 슬퍼하는 날의 수를 최소화하려고 합니다. 밥이 어떤 과목의 성적을 수정해야 할지 결정하도록 도와주세요.

첫째 날에는 앨리스가 항상 행복하다는 점을 참고하세요.

입력

첫 번째 줄에는 정수 $n$ ($1 \le n \le 4000$)이 주어집니다.

그다음 $n$개의 줄이 이어집니다. $i$번째 줄에는 두 정수 $A_i$와 $B_i$ ($0 \le A_i, B_i \le 400$)가 주어집니다.

출력

앨리스가 슬퍼하는 날의 최소 개수를 출력하세요.

예제

입력 1

4
1 2
2 3
1 2
1 1

출력 1

1