eolymp
bolt
Try our new interface for solving problems
Məsələlər

Коробки

Коробки

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 122 MiB

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

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

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

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
3
10 11
20 100
30 10
Çıxış verilənləri #1
3
Giriş verilənləri #2
3
11 11
20 100
30 10
Çıxış verilənləri #2
2