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

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

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

Input

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

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

Output

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