물은 답을 알고 있다

물은 생각할 수 있을까? 배울 수 있을까? 『물은 답을 알고 있다: 물 결정에 숨겨진 메시지』를 읽고 나면, 물이 사람의 감정을 비추고 듣고 보며 삶의 답을 아는 힘이 있다고 믿게 될지도 모른다.

『물은 답을 알고 있다』 서평, 마사루 에모토

그림: 『물은 답을 알고 있다: 물 결정에 숨겨진 메시지』의 표지

동현이는 $x$축을 땅으로 하는 2차원 평면에 산다. 이 평면에는 비가 많이 내리고, 비는 $y = +\infty$에서 떨어진다.

최근 동현이는 『물은 답을 알고 있다』를 읽고 깊은 인상을 받았다. 그는 이제 물이 삶의 답을 알려 줄 것이라고 믿는다.

동현이는 높이와 너비가 서로 다른 직사각형 상자 $N$개를 가지고 있다. 그는 빗물을 모으려고 상자들을 다시 배열하려 한다. 그러면 물이 삶의 답을 알려 준다. 이를 위해 상자들을 한 줄로 놓는다. 상자 사이에 빈 공간은 허용되지 않는다. 상자는 회전시키거나 그대로 둘 수 있지만, 모든 상자는 한 변이 땅에 닿아 있어야 한다.

물은 더 흐를 공간이 없을 때까지 왼쪽이나 오른쪽으로 흐른다. 정확히 말하면, 어떤 점의 물은 그 점이 상자 안에 있지 않고, 같은 높이의 왼쪽 어딘가와 오른쪽 어딘가에 상자가 있을 때 제자리에 머문다.

아래 그림은 가능한 예시이다. 회색 직사각형은 상자이고, 파란 영역은 물이다.

동현이가 저장할 수 있는 물의 최대 넓이는 얼마인가? (2차원 평면에서 넓이는 부피를 뜻한다.) 그는 아직 물이 없어서 답을 모른다. 당신은 답을 아는가?

입력은 $N+1$개의 줄로 이루어진다.

첫째 줄에 상자의 개수 $N$이 주어진다.

이어지는 $N$개의 줄에는 각 상자의 너비 $w_i$와 높이 $h_i$가 공백으로 구분되어 주어진다.

하나의 정수를 출력한다. 동현이가 상자를 최적으로 배열했을 때 저장할 수 있는 물의 최대 넓이이다.

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