사악한 과학자인 당신은 비밀 실험실에서 더 크고 무시무시한 젤리를 만드는 방법을 알아냈습니다. 원형 실험대 주위에는 $N$개의 직사각형 젤리가 순환 배열(cyclic array) 형태로 배치되어 있으며, 각 젤리는 특정 높이와 너비를 가지고 있습니다. 첫 번째 젤리와 마지막 젤리는 서로 인접해 있다는 점에 유의하세요.

두 개의 인접한 부모 젤리를 융합하면, 높이는 두 부모 젤리 높이의 최댓값이고 너비는 두 부모 젤리 너비의 최댓값인 결합된 젤리가 생성됩니다. 융합된 젤리는 순환 배열에서 부모 젤리들이 있던 자리를 대체하며(이때 배열의 길이는 1만큼 줄어듭니다), 원칙적으로는 다시 양옆의 이웃 중 하나와 융합될 수 있습니다.

당신은 이 융합 연산을 원하는 만큼 수행하여 젤리들의 넓이 합을 최대화하고자 합니다. 결국, 젤리가 차지하는 총 넓이가 클수록 더 많은 도시를 정복할 수 있기 때문입니다!

입력

첫 번째 줄에는 실험대에 처음에 놓인 젤리의 개수를 나타내는 정수 $N$ ($1 \le N \le 3 \cdot 10^5$)이 주어집니다.

다음 $N$개의 줄에는 이 젤리들에 대한 정보가 순서대로 주어집니다. $i$번째 줄에는 $i$번째 젤리의 높이와 너비를 나타내는 두 개의 정수 $h_i$와 $w_i$ ($1 \le h_i, w_i \le 10^6$)가 공백으로 구분되어 주어집니다.

출력

융합 연산을 원하는 만큼 수행하여 젤리들의 넓이 합을 최적으로 최대화했을 때, 순환 배열에 남아 있는 젤리들의 넓이 합을 하나의 정수로 출력하세요.

예제

입력 1

2
6 3
2 7

출력 1

42

입력 2

4
1 5
10 10
5 1
6 7

출력 2

152

입력 3

5
6 2
5 1
1 5
2 7
1 2

출력 3

67

입력 4

1
380385 222650

출력 4

84692720250