Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача E. Правила транспортировки

Задачу добавил: alef

Успешно сдано решений: 18

 

На описанных выше самоходных тележках, в частности, перевозят и прямоугольные пластины — заготовки для изготовления замков. С ними следует обращаться достаточно аккуратно, так что их укладывают стопкой таким образом, чтобы очередная пластина целиком помещалась на предыдущей. Стороны пластин должны быть строго параллельны друг другу (класть наискосок их нельзя).

Существует набор пластин из N штук (1 <= N <= 10000).

Необходимо определить, пластины какой максимально возможной общей площади можно загрузить в тележку при соблюдении правил транспортировки.


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


Первая строка — целое число N (1 <= N <= 10000) — количество пластин в наборе

В каждой из следующих N строк записано 2 целых числа через пробел — длина L и ширина W пластины (1 <= L, W <= 10000). Строка #j соответствует пластине #j-1


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


Первая строка — целое число S — максимально возможная суммарная площадь пластин, которые можно перевезти


Пример входного файла


8

7 7

5 5

3 3

8 8

1 1

4 4

2 2

6 3


Пример выходного файла


168


Сдать задачу

Задать вопрос жюри по этой задаче