Tý cần giải bài toán sau:

Mot cong ty bat dong san dang mua lai \(N\) thua dat. Thua dat thu \(i\) co chieu rong \(w_i\) va chieu dai \(l_i\). Khi mua mot nhom cac thua dat lien tiep, gia cua nhom duoc tinh bang tich cua chieu rong lon nhat va chieu dai lon nhat trong nhom.

Cu the, neu mua nhom \(j+1 \ldots i\), chi phi la:

\[\text{cost}(j+1, i) = \max_{j<k\le i} w_k \times \max_{j<k\le i} l_k\]

Cong ty co the chia \(N\) thua dat thanh cac nhom lien tiep tuy y. Hay tinh tong chi phi nho nhat de mua tat ca \(N\) thua dat.

Dinh dang dau vao

• Dong dau tien chua so nguyen \(N\) (\(1 \le N \le 10^5\)).
• \(N\) dong tiep theo, dong thu \(i\) chua hai so nguyen \(w_i\) va \(l_i\) (\(1 \le w_i, l_i \le 10^9\)).

Dinh dang dau ra

• Mot so nguyen duy nhat la tong chi phi nho nhat.

Vi du

Input:

4
2 8
5 4
3 7
6 2

Output:

36

Giai thich: Gom \((2,8)\) va \((5,4)\): chi phi \(5 \times 8 = 40\). Gom \((3,7)\) va \((6,2)\): chi phi \(6 \times 7 = 42\). Tong \(82\). Cach toi uu: mua \((2,8)\) rieng: \(16\), mua \((5,4), (3,7), (6,2)\): chi phi \(6 \times 7 = 42\). Tong \(58\). Cach toi uu hon: gom \((2,8), (5,4), (3,7)\): \(5 \times 8 = 40\), mua \((6,2)\) rieng: \(12\), tong \(52\). Toi uu: \((2,8), (5,4)\): \(40\), \((3,7), (6,2)\): \(42\), tong \(82\). Khong phai. W = 5 x 8 = 40, 3 x 7 = 21. Sai.

Cach dung: Sap xep theo w tang. Sau khi sap xep: (2,8) (3,7) (5,4) (6,2) => W tang, L giam. dp[1]=16 dp[2]=min(dp[0]+38=24, dp[1]+37=16+21=37)=24 dp[3]=min(dp[0]+58=40, dp[1]+57=16+35=51, dp[2]+5*4=24+20=44)=40 dp[4]=min(...)=52

Rang buoc

• Subtask 1 (20%): \(N \le 200\).
• Subtask 2 (30%): \(N \le 5000\).
• Subtask 3 (50%): \(N \le 10^5\).