402802: GYM100885 C The Last Number

На доске записано n целых чисел a₁, a₂, ..., a_n. Миша может стереть любые два числа a_i и a_j и вместо них записать их сумму a_i + a_j. При этом Миша выплачивает своему другу Жене количество монет, равное минимуму из этих двух стертых чисел.

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

В первой строке входных данных находится число n (1 ≤ n ≤ 10³). Во второй строке находится последовательность чисел a₁, a₂, ..., a_n, записанная через пробелы (1 ≤ a_i ≤ 10³).

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

2
7 3

3

3
10 20 30

30

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