Nguồn đề - Free Contest 116: https://drive.google.com/file/d/10Ef-xdNpLYw_tWZLzJ6JiRNex1qHcLda/view?usp=sharing

Lời giải: https://drive.google.com/file/d/1jTQ7gkNM9Fw8LIePpo3ffTsnnJAVBQl2/view

Cho N viên gạch, với viên gạch thứ i sẽ có 2 thông số đi kèm là ~a_i, b_i~. Nếu ta xếp viên gạch thứ i vào vị trí j thì độ xấu của nó sẽ được tính theo công thức sau.

~a_i~ x (j - 1) + ~b_i~ x (N - j)

Mỗi hoán vị của N viên gạch là một cách để sắp xếp các viên gạch với nhau. Bạn hãy tìm cách sắp xếp sao cho tổng độ xấu của các viên gạch là nhỏ nhất.

Input

• Dòng đầu tiên gồm 1 số nguyên N ~(1 \leq N \leq 10^5)~.

• N dòng tiếp theo, mỗi dòng gồm 2 số ~a_i, b_i~ ~(1 \leq a_i, b_i \leq 10^8 )~.

Output

• Gồm 1 số duy nhất là tổng độ xấu nhỏ nhất.

Sample Input 1

4
2 4
3 3
7 1
2 3

Sample Output 1

25

Giải thích

• Thứ tự sắp xếp sẽ là như sau: 3, 2, 4 ,1.

Chấm điểm

• Subtask 1 (20% số test): ~1 \leq N \leq 10~.
• Subtask 2 (30% số test): ~10 \leq N \leq 1000~.
• Subtask 3 (50% số test): Không có ràng buộc gì thêm.