XEPGACH

Cho N viên gạch, với viên gạch thứ i sẽ có 2 thông số đi kèm là ai, bi. 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:ai × (j − 1) + bi × (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 khi sắp xếp các viên gạch.

Dữ liệu

• Dòng đầu tiên gồm 1 số nguyên N (1 ≤ N ≤ 105). • N dòng tiếp theo, mỗi dòng gồm 2 số ai, bi (1 ≤ ai, bi ≤ 10^8)

Kết quả

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

Sample Input

4 2 4 3 3 7 1 2 3

Sample Output

25