시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 (언어별 추가 시간 없음) 1024 MB 216 37 21 58.333%

문제

Can water think? Can it learn? After reading the book Water Knows the Answers — the Hidden Messages in Water Crystals, you may believe that water can reflect human emotions and has the power to listen, see, and know the answers to life.

— Review of the book Water Knows the Answers, by Masaru Emoto

Figure: The cover of the book Water Knows the Answers — the Hidden Messages in Water Crystals

Donghyun lives in a 2D plane, having $x$-axis as ground. It rains a lot in the 2D plane, and the rain falls from $y = +\infty$.

Recently, Donghyun read a book called Water Knows the Answers — the Hidden Messages in Water Crystals, and got impressed by the book. He now believes that water will tell him the answers to life.

Donghyun has $N$ rectangular boxes with (possibly) different heights and widths. He is going to rearrange those boxes in order to collect the rainfall. Then, the water will give him the answers to life. To achieve this, he is going to place the box in a row. No empty space is allowed between the boxes. He may rotate some of the boxes or not, but he should make its edges parallel to the ground.

The water can flow left or right until it has no space to flow to. Formally, water in certain point can stay in its place if that point is not inside the box and has a box both somewhere to its left and somewhere to its right at the same height.

Donghyun wants to know the maximum area of water he can store. (In the 2D plane, area means volume.) But, he doesn't have water yet, so he doesn't know the answer. Do you know the answer?

입력

Input consists of $N+1$ lines.

In the first line, the number of boxes $N$ is given.

Next $N$ lines contains the width $w_i$ and height $h_i$ of each boxes, space-separated.

출력

Print a single integer, denoting the maximum area of water Donghyun can store if he arrange the boxes optimally.

제한

  • $3 \le N \le 250,000$
  • $1 \le w_i,\ h_i \le 10^6$

서브태스크 1 (18점)

This subtask has an additional constraint:

  • $N = 3$

서브태스크 2 (19점)

This subtask has an additional constraint:

  • $w_i = h_i$

서브태스크 3 (34점)

This subtask has an additional constraint:

  • $N \le 100$

서브태스크 4 (14점)

This subtask has an additional constraint:

  • $N \le 2\,500$

서브태스크 5 (15점)

This subtask has no additional constraints.

예제 입력 1

3
4 3
2 6
5 1

예제 출력 1

15


 

출처

University > KAIST > 2019 KAIST RUN Spring Open Contest E번

채점

  • 예제는 채점하지 않는다.