#P524B. Фото на память - 2 (round version)
Фото на память - 2 (round version)
Cannot parse: NaNs error parsing time
Description
Прошло много лет, и на вечеринке снова встретились n друзей. С момента последней встречи техника шагнула далеко вперёд, появились фотоаппараты с автоспуском, и теперь не требуется, чтобы один из друзей стоял с фотоаппаратом, и, тем самым, оказывался не запечатлённым на снимке.
Упрощенно процесс фотографирования можно описать следующим образом. На фотографии каждый из друзей занимает прямоугольник из пикселей: в стоячем положении i-й из них занимает прямоугольник ширины wi пикселей и высоты hi пикселей. Но также, при фотографировании каждый человек может лечь, и тогда он будет занимать прямоугольник ширины hi пикселей и высоты wi пикселей.
Общая фотография будет иметь размеры W × H, где W — суммарная ширина всех прямоугольников-людей, а H — максимальная из высот. Друзья хотят определить, какую минимальную площадь может иметь общая фотография. Помогите им в этом.
В первой строке следует целое число n (1 ≤ n ≤ 1000) — количество друзей.
В последующих n строках следуют по два целых числа wi, hi (1 ≤ wi, hi ≤ 1000), обозначающие размеры прямоугольника, соответствующего i-му из друзей.
Выведите единственное целое число, равное минимальной возможной площади фотографии, вмещающей всех друзей.
Input
В первой строке следует целое число n (1 ≤ n ≤ 1000) — количество друзей.
В последующих n строках следуют по два целых числа wi, hi (1 ≤ wi, hi ≤ 1000), обозначающие размеры прямоугольника, соответствующего i-му из друзей.
Output
Выведите единственное целое число, равное минимальной возможной площади фотографии, вмещающей всех друзей.
Samples
3
10 1
20 2
30 3
180
3
3 1
2 2
4 3
21
1
5 10
50