C. Мониторы

Имя входного файла:	monitors.in
Имя выходного файла:	monitors.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

Чёрный Кот подрабатывает созданием сайтов на заказ. Одной из необходимых операций для создания сайта является вёрстка макета – когда макет дизайна, нарисованный в графическом редакторе, переводят в HTML, чтобы потом на основе этого HTML-документа создать шаблон для системы управления содержимым сайта.

Конечно, при вёрстке HTML-шаблона, Кот проверяет правильность его отображения в различных условиях: в разных браузерах, с разным разрешением экрана и т.п. Обычно всё проходит достаточно гладко, однако в этот раз заказчик хочет, чтобы сайт корректно отображался на очень широких мониторах (более 2000 пикселов по горизонтали). Однако у Кота нет такого широкого монитора и казалось бы, он не сможет протестировать сайт. Но Кот не был бы Котом, если бы не придумал решение. Он понял, что если подключить к компьютеру несколько мониторов и расположить их по горизонтали, можно получить достаточно широкий виртуальный экран, на котором уже можно будет протестировать сайт. Кот выписал разрешения всех мониторов, которые есть у него и его друзей и теперь хочет узнать, какое же максимальное разрешение по горизонтали он может получить, используя эти мониторы.

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

Формат входного файла

В первой строке входного файла находится единственное число N – количество мониторов, имеющихся у Кота и его друзей (1 ≤ N ≤ 100000). Далее в N строках следует по два числа w_i, h_i – разрешение очередного монитора по горизонтали и вертикали соответственно (1 ≤ w_i, h_i ≤ 10⁹).

Формат выходного файла

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

Пример:

monitors.in	monitors.out
3 1024 768 1024 768 1600 1200	2048
4 1024 768 1024 768 1600 1200 1600 1200	3200
3 640 480 800 600 400 768	800

Примечание: в первом примере Коту следует объединить два первых монитора. Третий монитор добавить к ним нельзя, поскольку у него другое разрешение по вертикали. Во втором примере можно объединить либо два первых монитора, либо два последних. Два последних объединить выгоднее. В третьем примере никакие два монитора объединить нельзя – Коту придётся просто использовать самый широкий монитор.

Источник: VI Сетевая районная олимпиада Республики Карелия по информатике. 3 декабря 2011 г. XXIII Городская олимпиада школьников г. Петрозаводска по информатике
Автор: Денис Денисов

Обсудить       Отправить решение