A9809 | Фото на память - 2 (round version)

Photo for memory - 2 (round version)
照片记忆 - 2 (圆形版本)

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

Упрощенно процесс фотографирования можно описать следующим образом. На фотографии каждый из друзей занимает прямоугольник из пикселей: в стоячем положении $i$ -й из них занимает прямоугольник ширины $w_{i}$ пикселей и высоты $h_{i}$ пикселей. Но также, при фотографировании каждый человек может лечь, и тогда он будет занимать прямоугольник ширины $h_{i}$ пикселей и высоты $w_{i}$ пикселей.

Общая фотография будет иметь размеры $W×H$ , где $W$ — суммарная ширина всех прямоугольников-людей, а $H$ — максимальная из высот. Друзья хотят определить, какую минимальную площадь может иметь общая фотография. Помогите им в этом.

В первой строке следует целое число $n$ ( $1<=n<=1000$ ) — количество друзей.

В последующих $n$ строках следуют по два целых числа $w_{i},h_{i}$ ( $1<=w_{i},h_{i}<=1000$ ), обозначающие размеры прямоугольника, соответствующего $i$ -му из друзей.