En este semestre, Alice tomó $n$ cursos. Ahora, ha terminado todos los exámenes finales y recibirá sus calificaciones en los próximos $n$ días.

En el día $i$-ésimo, Alice conocerá su calificación $A_i$ del curso $i$-ésimo. Si $A_i$ es estrictamente menor que el promedio de las calificaciones de los primeros $i - 1$ cursos, Alice estará triste ese día.

Ahora, Bob está hackeando la base de datos de la universidad. Bob puede elegir un conjunto $S$ de cursos ($S$ puede estar vacío). Luego, para cada curso $i$ en $S$, puede cambiar la calificación de Alice de $A_i$ a $B_i$.

Bob quiere minimizar el número de días en los que Alice estará triste. Ahora necesitas ayudarle a decidir qué calificaciones de los cursos debe modificar.

Ten en cuenta que Alice siempre estará feliz el primer día.

Entrada

La primera línea contiene un único entero $n$ ($1 \le n \le 4000$).

Luego siguen $n$ líneas. La $i$-ésima de estas líneas contiene dos enteros, $A_i$ y $B_i$ ($0 \le A_i, B_i \le 400$).

Salida

Imprime el número mínimo de días en los que Alice estará triste.

Ejemplos

Entrada 1

4
1 2
2 3
1 2
1 1

Salida 1

1