Задача 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