Hôm nay, được dịp nghỉ lễ nên bố Kaninho dắt Kaninho ra vườn và đố anh ta một bài toán như sau:

Có \(n\) cái cây được sắp xếp trên trục toạ độ \(Ox\) có toạ độ lần lượt là : \(X_1,X_2,...,X_n\) và chiều cao tương ứng lần lượt là: \(H_1,H_2,...,H_n\)

• "Độ chênh lệch xa" của \(2\) cái cây bất kì được xác định như sau:

• Đầu tiên ta sẽ sắp xếp lại tất cả các cái cây theo tứ tự tăng dần theo toạ độ . Cây có toạ độ nhỏ nhất sẽ có thứ tự là \(1\). Những cây nào có cùng toạ độ thì sẽ cùng thứ tự. Ví dụ, ta có \(5\) cái cây có toạ độ lần lượt là \(3,3,1,3,4\) thì thứ tự của chúng sẽ lần lượt là: \(2,2,1,2,5\).

• Khi đó "độ chênh lệch xa" của hai cái cây thứ \(i\) và thứ \(j\) bất kì sẽ là \(|D_i-D_j|\) - Trong đó: \(D_i,D_j\) là thứ tự của hai cây thứ i và \(j\) sau khi đã được sắp xếp.

• Tiếp theo: "Độ chênh lệch cao" của \(2\) cái cây bất kì được xác định như sau:

• Đầu tiên ta sẽ sắp xếp lại tất cả các cái cây theo tứ tự tăng dần theo chiều cao . Cây có chiều cao nhỏ nhất sẽ có thứ tự là \(1\). Những cây nào có cùng chiều cao thì sẽ cùng thứ tự. Ví dụ, ta có \(5\) cái cây có chiều cao lần lượt là \(4,1,9,7,4\) thì thứ tự của chúng sẽ lần lượt là: \(2,1,5,4,2\).

• Khi đó "độ chênh lệch cao" của hai cái cây thứ \(i\) và thứ \(j\) bất kì sẽ là \(min(E_i,E_j)\) - Trong đó: \(E_i,E_j\) là thứ tự của hai cây thứ \(i\) và \(j\) sau khi đã được sắp xếp.

• Cuối cùng "độ tương thích" của hai cái cây bất kì chính bằng tích của "độ chênh lệch xa" và "độ chênh lệch cao" của hai cây đó

Yêu cầu: Tính tổng "độ tương thích" của tất cả các cặp cây trên.

Input

• Đề bài sẽ có nhiều testcase, mỗi test có dạng như sau:

• Dòng thứ nhất chứa số \(n\) \((2\le n\le 10^5)\) - Thể hiện số lượng cây.

• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(X_i\), \(H_i\) (\(0 <\) \(X_i\), \(H_i\) \(\le\) \(10^9\)) - Thể hiện toạ độ và chiều cao của cây thứ \(i\)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm

Scoring

• Subtask \(1\) (\(37.5\%\) số điểm): \(1\le n \le 20\) ; \(0<X_i,H_i\le 50\).

• Subtask \(1\) (\(62.5\%\) số điểm): không có điều kiện gì thêm.

Example

2
3 4
4 5
3
7 8
9 8
6 5

1
5