У Фермера Джона есть ферма, состоящая из \(n\) пастбищ, соединенных с помощью односторонних дорог. У каждой дороги есть вес, означающий время, которое необходимо потратить, чтобы пройти по ней. Дороги могут иметь отрицательный вес, иными словами, коровы по ним движутся так быстро, что способны перемещаться назад во времени! Однако, Фермер Джон гарантирует, что коровы никак не смогут попасть во временную петлю в том смысле, что не смогут, двигаясь по дорогам, уйти бесконечно далеко в прошлое. Кроме того, каждая пара пастбищ соединена не более чем одной дорогой в каждом направлении.
К сожалению, Фермер Джон потерял карту фермы. Все, что он знает — это массив \(d\), где \(d_i\) — это минимальное время, за которое коровы могут добраться до \(i\)-го пастбища из \(1\)-го, двигаясь по дорогам. Стоимость его фермы — это сумма весов всех дорог, и Фермер Джон хочет узнать минимально возможную стоимость фермы, которая не противоречит тому, что он помнит.
Выходные данные
Для каждого набора, выведите минимально возможную стоимость фермы, которая не противоречит воспоминаниям Фермера Джона.
Примечание
В первом наборе вы можете добавить дороги
- от пастбища \(1\) к пастбищу \(2\) с весом \(2\),
- от пастбища \(2\) к пастбищу \(3\) с весом \(1\),
- от пастбища \(3\) к пастбищу \(1\) с весом \(-3\),
- от пастбища \(3\) к пастбищу \(2\) с весом \(-1\),
- от пастбища \(2\) к пастбищу \(1\) с весом \(-2\).
Суммарная стоимость равна
\(2 + 1 + -3 + -1 + -2 = -3\).
Во втором набор вы можете добавить дорогу от пастбища \(1\) к пастбищу \(2\) с весом \(1000000000\) и дорогу от пастбища \(2\) к пастбищу \(1\) со стоимостью \(-1000000000\). Суммарная стоимость равна \(1000000000 + -1000000000 = 0\).
В третьем наборе, вы не можете добавить ни одной дороги. Суммарная стоимость равна \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
0 2 3
2
0 1000000000
1
0
|
-3
0
0
|