Молодой и амбициозный управляющий транспортной компании Платон получил крупный заказ на доставку товаров из столицы сразу в n городов страны. Между каждым городом и столицей проложена дорога. Других дорог в стране нет.
Длина дороги от столицы до города с номером i равна di километров. По иронии судьбы, в этот же город компания должна доставить ровно di тонн груза.
Грузовик Платона загружается один раз в столице. Затем Платон начинает процесс доставки грузов. Конечно же, Платон способен перемещаться только по дорогам. Он может посещать города в любом порядке, оставляя в них часть груза. В стране действует система налогообложения, и для перевозки m тонн товара по дороге длиной l километров требуется заплатить в казну m × l рублей. Помогите Платону рассчитать минимальный размер налогов, который компания должна заплатить для успешной доставки всех товаров.
Исходные данные
В первой строке дано целое число n (1 ≤ n ≤ 105) — количество городов, в которые нужно доставить товар. Во второй строке даны n целых чисел разделённых пробелом, i-тое из которых di (1 ≤ di ≤ 104) — длина дороги в город i.
Результат
В единственной строке выведите минимальный размер налога, который заплатит компания.
Пример
исходные данные | результат |
---|
3
1 2 3
| 36
|
Автор задачи: Анна Ханова
Источник задачи: Вузовско-академическая олимпиада по информатике 2019