28. Села батарейка (2.0)

Производители умных часов стараются заботиться о наилучшем пользовательском опыте. Чтобы часы выполняли свои функции, в них постоянно должны быть активны $n$ приложений. Один из важных показателей работы устройства $-$ то, сколько часов оно сможет работать без подзарядки. Экспериментальным путём для каждого приложения было выяснено, сколько процентов батареи оно тратит в час. Вам подарили вторые часы и распределили $n$ приложений по двум устройствам так, что каждое приложение содержится ровно на одном устройстве. Однако вы знаете, что приложения могли быть распределены не наилучшим образом, и вы хотите оценить, какое минимальное суммарное количество времени будут работать два устройства в худшем случае.

В первой строке содержится целое число $2 \le n \le 5 \cdot 10^5$ $-$ количество стандартных приложений. В следующей строке содержится ровно $n$ целых чисел $1 \le a_i \le 10000$, $i$-е из которых обозначает, сколько сотых процента заряда батареи в час съедает приложение $i$.

В единственной строке выведите одно целое число, обозначающее суммарное количество полных часов, которое проработают два устройства при наихудшем распределении приложений между ними(то есть минимально возможное суммарное время).

Суммарное время вычисляется как количество полных часов, которое будет работать первое устройство, плюс количество полных часов, которое будет работать второе устройство. Например, если первое устройство будет работать $2.7$ часа, а второе $-$ $1.8$ часа, то ответ будет равен $2 + 1 = 3$.