D. Стас и очередь в буфет
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На перемене в буфете научного лицея Королевства Кремляндия образовалась очередь из $$$n$$$ лицеистов, пронумерованных от $$$1$$$ до $$$n$$$. Изначально каждый ученик $$$i$$$ стоит на позиции $$$i$$$. Каждый ученик $$$i$$$ характеризуется двумя числами — $$$a_i$$$ и $$$b_i$$$. Недовольство лицеиста $$$i$$$ равняется произведению $$$a_i$$$ на количество людей, стоящих слева от его позиции, прибавить произведение $$$b_i$$$ на количество людей, стоящих справа от его позиции. Формально, недовольство ученика $$$i$$$, который стоит на позиции $$$j$$$, равняется $$$a_i \cdot (j-1) + b_i \cdot (n-j)$$$.

Директор поручил Стасу задание: переставить людей в очереди так, чтобы минимизировать суммарное недовольство.

Хоть Стас и умеет решать подобные задачи, но эта ему не далась. Он обратился за помощью к вам.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — количество человек в очереди.

Каждая из следующих $$$n$$$ строк содержит два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \leq a_i, b_i \leq 10^8$$$) — характеристика ученика $$$i$$$, изначально стоящего на позиции $$$i$$$.

Выходные данные

Выведите одно целое число — минимальное суммарное недовольство которого можно достичь, переставляя людей в очереди.

Примеры
Входные данные
3
4 2
2 3
6 1
Выходные данные
12
Входные данные
4
2 4
3 3
7 1
2 3
Выходные данные
25
Входные данные
10
5 10
12 4
31 45
20 55
30 17
29 30
41 32
7 1
5 5
3 15
Выходные данные
1423
Примечание

В первом примере оптимально поставить людей в таком порядке: ($$$3, 1, 2$$$). Первый человек стоит на позиции $$$2$$$, тогда его недовольство будет равно $$$4 \cdot 1+2 \cdot 1=6$$$. Второй человек стоит на позиции $$$3$$$, его недовольство будет равно $$$2 \cdot 2+3 \cdot 0=4$$$. Третий человек стоит на позиции $$$1$$$, его недовольство будет равно $$$6 \cdot 0+1 \cdot 2=2$$$. Суммарное недовольство равно $$$12$$$.

Во втором примере необходимо поставить людей в таком порядке: ($$$3, 2, 4, 1$$$). Суммарное недовольство равно $$$25$$$.