В этом семестре Алиса изучала $n$ курсов. Она закончила все выпускные экзамены и будет получать оценки в течение следующих $n$ дней.

В $i$-й день Алиса узнает свою оценку $A_i$ за $i$-й курс. Если $A_i$ строго меньше среднего арифметического оценок за первые $i - 1$ курсов, Алиса будет расстроена в этот день.

Боб взламывает базу данных университета. Боб может выбрать множество курсов $S$ ($S$ может быть пустым). Затем для каждого курса $i$ из $S$ он может изменить оценку Алисы с $A_i$ на $B_i$.

Боб хочет минимизировать количество дней, когда Алиса будет расстроена. Вам нужно помочь ему решить, оценки за какие курсы ему следует изменить.

Заметьте, что Алиса всегда будет счастлива в первый день.

Входные данные

Первая строка содержит единственное целое число $n$ ($1 \le n \le 4000$).

Затем следуют $n$ строк. $i$-я из этих строк содержит два целых числа $A_i$ и $B_i$ ($0 \le A_i, B_i \le 400$).

Выходные данные

Выведите минимальное количество дней, когда Алиса будет расстроена.

Примеры

Входные данные 1

4
1 2
2 3
1 2
1 1

Выходные данные 1

1