Ce semestre, Alice a suivi $n$ cours. Elle a maintenant terminé tous ses examens finaux et recevra ses notes au cours des $n$ jours suivants.

Le $i$-ième jour, Alice connaîtra sa note $A_i$ du $i$-ième cours. Si $A_i$ est strictement inférieure à la moyenne des notes des $i - 1$ premiers cours, Alice sera triste ce jour-là.

Bob pirate la base de données de l'université. Bob peut choisir un ensemble $S$ de cours ($S$ peut être vide). Ensuite, pour chaque cours $i$ dans $S$, il peut modifier la note d'Alice de $A_i$ à $B_i$.

Bob souhaite minimiser le nombre de jours où Alice sera triste. Vous devez l'aider à décider quels cours il doit modifier.

Notez qu'Alice sera toujours heureuse le premier jour.

Entrée

La première ligne contient un entier unique $n$ ($1 \le n \le 4000$).

Les $n$ lignes suivantes suivent. La $i$-ième de ces lignes contient deux entiers, $A_i$ et $B_i$ ($0 \le A_i, B_i \le 400$).

Sortie

Affichez le nombre minimum de jours où Alice sera triste.

Exemples

Entrée 1

4
1 2
2 3
1 2
1 1

Sortie 1

1