{"code":"xavcao","name":"Kaninho và bài toán \"độ tương thích\" của những cái cây","description":"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:\r\n\r\nCó $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$\r\n\r\n- **\"Độ chênh lệch xa\"** của $2$ cái cây bất kì được xác định như sau:\r\n\r\n + Đầ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$.\r\n\r\n + 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.\r\n\r\n- Tiếp theo: **\"Độ chênh lệch cao\"** của $2$ cái cây bất kì được xác định như sau:\r\n\r\n + Đầ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$.\r\n\r\n + 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.\r\n\r\n- 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 đó\r\n\r\n**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.\r\n\r\n

Input

\r\n\r\n- Đề bài sẽ có nhiều testcase, mỗi test có dạng như sau:\r\n\r\n + Dòng thứ nhất chứa số $n$ $(2\\le n\\le 10^5)$ - Thể hiện số lượng cây.\r\n\r\n + $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$\r\n\r\n

Output

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

Scoring

\r\n\r\n+ Subtask $1$ ($37.5\\%$ số điểm): $1\\le n \\le 20$ ; $0Example\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 2\r\n 3 4\r\n 4 5\r\n 3\r\n 7 8\r\n 9 8\r\n 6 5\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 1\r\n 5\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n Ứng với testcase $1$,ta có: Tổng **\"độ tương thích\"** của tất cả các cặp cây là: $1 * 1=1$\r\n\r\n Ứng với testcase $2$, ta có: Tổng **\"độ tương thích\"** của tất cả các cặp cây là: $1 * 2+2*1+1*1=5$","points":550.0,"partial":false,"time_limit":2.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}