今学期、アリスは $n$ 個のコースを受講しました。現在、彼女はすべての期末試験を終え、今後 $n$ 日間にわたって成績を受け取ることになっています。

$i$ 日目に、アリスは $i$ 番目のコースの成績 $A_i$ を知ります。もし $A_i$ が最初の $i-1$ 個のコースの平均成績よりも真に小さい場合、アリスはその日に悲しみます。

ボブは大学のデータベースにハッキングしています。ボブはコースの集合 $S$ （空集合でもよい）を選択し、集合 $S$ に含まれる各コース $i$ について、アリスの成績を $A_i$ から $B_i$ に変更することができます。

ボブはアリスが悲しむ日数を最小化したいと考えています。どのコースの成績を変更すべきか決定するのを手伝ってください。

なお、アリスは初日には必ず幸せであることに注意してください。

入力

1行目に整数 $n$ ($1 \le n \le 4000$) が与えられます。 続く $n$ 行には、各コースの成績に関する情報が与えられます。$i$ 番目の行には2つの整数 $A_i$ と $B_i$ ($0 \le A_i, B_i \le 400$) が含まれています。

出力

アリスが悲しむ日数の最小値を出力してください。

入出力例

入力 1

4
1 2
2 3
1 2
1 1

出力 1

1