402802: GYM100885 C The Last Number

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Последнее числоограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводlast.inвыводlast.out

На доске записано n целых чисел a1, a2, ..., an. Миша может стереть любые два числа ai и aj и вместо них записать их сумму ai + aj. При этом Миша выплачивает своему другу Жене количество монет, равное минимуму из этих двух стертых чисел.

Миша хочет оставить на доске ровно одно число, отдав Жене как можно меньше монет. Помогите ему в этом.

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

В первой строке входных данных находится число n (1 ≤ n ≤ 103). Во второй строке находится последовательность чисел a1, a2, ..., an, записанная через пробелы (1 ≤ ai ≤ 103).

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

Выведите единственное число — минимальное количество монет, которое необходимо Мише заплатить Жене, чтобы на доске осталось ровно одно число.

ПримерыВходные данные
2
7 3
Выходные данные
3
Входные данные
3
10 20 30
Выходные данные
30
Примечание

Во втором примере Миша может сначала стереть числа 20 и 30 и записать на доске число 50. Затем стереть числа 10 и 50 и записать 60. Итого Миша должен отдать Жене 20 + 10 = 30 монет.

加入题单

上一题 下一题 算法标签: