作為一名邪惡科學家，你已經研究出如何在你的秘密實驗室中製造更大、更可怕的果凍。在你的圓形實驗台周圍排列著一個包含 $N$ 個矩形果凍的循環陣列（cyclic array），每個果凍都有特定的高度和寬度。請注意，第一個和最後一個果凍是相鄰的。

果凍融合示意圖。

你可以將兩個相鄰的父果凍融合在一起，產生一個高度等於兩個父果凍高度之最大值、寬度等於兩個父果凍寬度之最大值的組合果凍。融合後的果凍會取代循環陣列中原本父果凍的位置（陣列長度減少 1），並且原則上可以再次與其兩個鄰居之一進行融合。

你希望透過執行任意次數的融合操作，使所有果凍的面積總和最大化。畢竟，你的果凍覆蓋的總面積越大，你能征服的城市就越多！

輸入格式

第一行包含一個整數 $N$ ($1 \le N \le 3 \cdot 10^5$)，代表實驗台上最初的果凍數量。

接下來的 $N$ 行依序描述這些果凍。第 $i$ 行包含兩個以空格分隔的整數 $h_i$ 和 $w_i$ ($1 \le h_i, w_i \le 10^6$)，分別代表第 $i$ 個果凍的高度與寬度。

輸出格式

輸出一個整數：在執行任意次數的融合操作以達到面積總和最大化後，循環陣列中剩餘果凍的面積總和。

範例

輸入 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