CF524B.Фото на память - 2 (round version)

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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$ -му из друзей.

输入输出样例

输入#1
```
3
10 1
20 2
30 3
```
输出#1
```
180
```
输入#2
```
3
3 1
2 2
4 3
```
输出#2
```
21
```
输入#3
```
1
5 10
```
输出#3
```
50
```

首页