На перемене в буфете научного лицея Королевства Кремляндия образовалась очередь из \(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)\).
Директор поручил Стасу задание: переставить людей в очереди так, чтобы минимизировать суммарное недовольство.
Хоть Стас и умеет решать подобные задачи, но эта ему не далась. Он обратился за помощью к вам.
Выходные данные
Выведите одно целое число — минимальное суммарное недовольство которого можно достичь, переставляя людей в очереди.
Примечание
В первом примере оптимально поставить людей в таком порядке: (\(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 2
2 3
6 1
|
12
|
|
2
|
4
2 4
3 3
7 1
2 3
|
25
|
|
3
|
10
5 10
12 4
31 45
20 55
30 17
29 30
41 32
7 1
5 5
3 15
|
1423
|