本学期，Alice 修读了 $n$ 门课程。现在，她已经完成了所有的期末考试，并将在接下来的 $n$ 天内陆续得知她的成绩。

在第 $i$ 天，Alice 会得知第 $i$ 门课程的成绩 $A_i$。如果 $A_i$ 严格小于前 $i-1$ 门课程的平均成绩，Alice 在这一天会感到难过。

现在，Bob 正在入侵大学的数据库。Bob 可以选择一个课程集合 $S$（$S$ 可以为空）。对于集合 $S$ 中的每一门课程 $i$，他可以将 Alice 的成绩从 $A_i$ 修改为 $B_i$。

Bob 希望最小化 Alice 感到难过的天数。你需要帮助他决定应该修改哪些课程的成绩。

注意：Alice 在第一天总是开心的。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 4000$)。

接下来 $n$ 行，第 $i$ 行包含两个整数 $A_i$ 和 $B_i$ ($0 \le A_i, B_i \le 400$)。

输出格式

输出 Alice 感到难过的最少天数。

样例

输入 1

4
1 2
2 3
1 2
1 1

输出 1

1