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

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

Общая фотография будет иметь размеры W × H, где W — суммарная ширина всех прямоугольников-людей, а H — максимальная из высот. Друзья хотят определить, какую минимальную площадь может иметь общая фотография, если лечь может не более половины всех друзей (ведь будет странно, если больше n / 2 солидных джентльменов будут лежать на фотографии, не так ли?)

Помогите им в этом.