<ПРЕД Задача:
СЛЕД>
Задачу решили 963 пользователя: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Атлеты

Time limit = 3 секунд(ы)

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

Каждый атлет характеризуется силой si (in kg) и массой mi (in kg). Сила — это максимальная масса, которую атлет способен держать у себя на плечах.

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

Вход Первая строчка входа содержит число n атлетов а далее следуют n строчек с их параметрами:

n
m1 s1
m2 s2
...
mn sn

Известно, что если атлет тяжелее, то он и сильнее:

если mi>mj, то si > sj.

Но атлеты равной массы могут иметь различную силу.

Число атлетов 1 ≤ n ≤ 100000. Масса и сила являются положительными целыми числами меньше, чем 2000000.

Выход Выход должен содержать натуральное число — максимальную высоту башни.

Вход#1
4
3 4
2 2
7 6
4 5
Выход#1
3

Автор:
Ворожцов Артем

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 230ms

SW soft NIX
ID = 3.228.10.17