eolymp
bolt
Try our new interface for solving problems
Problems

Коробки

Коробки

Time limit 1 second
Memory limit 122 MiB

У Васи в комнате очень много коробок, которые валяются в разных местах. Васина мама хочет, чтобы он прибрался. Свободного места в комнате мало и поэтому Вася решил собрать все коробки и составить их одну на другую.

К сожалению, это может быть невозможно. Например, если на картонную коробку с елочными украшениями положить что-то железное и тяжелое, то вероятно следующий Новый год придется встречать с новыми игрушками.

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

Input data

Первая строка входного файла содержит целое число n (1n10^5) — количество коробок в комнате. Каждая следующая из n строк содержит два целых числа w_i и c_i (1w_i10^5, 1c_i10^9), где w_i – это вес коробки с номером i, а c_i – это вес который она может выдержать.

Output data

В выходной файл выведите одно число — ответ на задачу.

Examples

Input example #1
3
10 11
20 100
30 10
Output example #1
3
Input example #2
3
11 11
20 100
30 10
Output example #2
2