21101번 - GPA 다국어

문제

In this semester, Alice took $n$ courses. Now, she has finished all the final exams. And she will get her grades in the following $n$ days.

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

Now Bob is hacking into the university's database. Bob can choose a set $S$ of courses ($S$ can be empty). And 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 when Alice will be sad. Now you need to help him to decide which courses' grades he should modify.

Note that Alice will always be happy on the first day.

입력

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

Then $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 the minimum number of days when Alice will be sad.

제한

힌트