GPA

Time limit1sMemory limit256 MB

Summary

Given n courses with original grade A_i and altered grade B_i, pick a subset to change so the number of days where the new grade falls below the running average of earlier grades is minimized.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Sorting, Prefix sum
Solved: No attempts yet

Problem

This semester, Alice took $n$ courses. She has now finished all her final exams, and over the next $n$ days she will receive her grades.

On the $i$ -th day, Alice learns her grade $A_i$ in the $i$ -th course. If $A_i$ is strictly less than the average grade of the first $i - 1$ courses, Alice is sad that day.

Bob has broken into the university's database. He can choose a set $S$ of courses ( $S$ may be empty). Then, for each course $i$ in $S$ , he can change Alice's grade from $A_i$ to $B_i$ .

Bob wants to minimize the number of days Alice is sad. Help him decide which courses' grades he should change.

Alice is always happy on the first day.

Input

The first line contains a single integer $n$ ( $1 \le n \le 4000$ ).

The next $n$ lines follow. The $i$ -th of these lines contains two integers $A_i$ and $B_i$ ( $0 \le A_i, B_i \le 400$ ).

Output

Output the minimum number of days Alice is sad.

Examples1

Example 1
Input
```
4
1 2
2 3
1 2
1 1
```
Expected output
```
1
```