철판 자르기

ISCO(ICPC Steel Company)는 특정 모양의 강철판을 사서 조각으로 자른 뒤 업계 시장에 판매하는 회사이다. ISCO가 사들이는 강철판은 모두 구멍이 없는 다각형이며, 각 변은 $x$축에 대해 수평 또는 수직이다. 각 변의 길이는 양의 정수이다. 이런 다각형을 히스토곤이라고 부른다. 그림 1(a)에 히스토곤이 나와 있다.

그림 1. (a) 히스토곤 모양의 강철판. (b) 히스토곤에 포함된 면적이 최대인 축 정렬 직사각형(빨간색). (c) 히스토곤을 수직선을 따라 너비 1인 직사각형 슬랩 8개로 나눈 모습.

면적이 큰 직사각형일수록 조각의 시장 가격이 훨씬 높으므로, ISCO는 면적이 최대인 직사각형을 얻도록 강철판을 자르려 한다. 과제는 강철판에 포함되는 축 정렬 직사각형 중 면적이 가장 큰 것을 찾는 것이다. 직사각형의 각 변은 $x$축에 대해 수평 또는 수직이어야 한다. 그림 1(b)는 그림 1(a)의 히스토곤에서 면적이 최대인 직사각형을 보여준다.

너비가 $n$인 히스토곤은 수직선을 따라 너비 1인 직사각형 슬랩 $n$개로 나눌 수 있다. 그림 1(c)는 그림 1(a)를 슬랩 8개로 나눈 것이다. 슬랩은 왼쪽부터 1에서 $n$까지 번호가 매겨지며, 가장 왼쪽 슬랩의 번호는 1이다. $x$축은 모든 슬랩과 교차한다고 가정한다. 슬랩 $i$는 두 값 $h_i$와 $l_i$로 나타낸다. $h_i$는 슬랩 $i$의 $x$축 위쪽 세로 길이이고, $l_i$는 아래쪽 세로 길이이다.

너비가 $n$인 히스토곤이 주어졌을 때, 히스토곤에 포함되는 축 정렬 직사각형의 면적 최댓값을 구하시오.

첫 줄에 히스토곤의 너비 $n$($1 \le n \le 200{,}000$)이 주어진다. 슬랩은 왼쪽 끝을 1번으로 하여 1번부터 $n$번까지 번호가 매겨진다. 이어지는 $n$개의 줄 중 $i$번째 줄에는 슬랩 $i$를 나타내는 두 음이 아닌 정수 $h_i$와 $l_i$($0 \le h_i, l_i \le 1{,}000{,}000{,}000$)가 주어진다.

주어진 히스토곤에 포함되는 축 정렬 직사각형 면적의 최댓값을 한 줄에 출력한다.