Прошло много лет, и на вечеринке снова встретились 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-му из друзей.

-----Выходные данные-----

Выведите единственное целое число, равное минимальной возможной площади фотографии, вмещающей всех друзей.

-----Примеры----- Входные данные 3 10 1 20 2 30 3

Выходные данные 180

Входные данные 3 3 1 2 2 4 3

Выходные данные 21

Входные данные 1 5 10

Выходные данные 50