~/algor $ cat masalalar/ochkoz-navbatda-kutish
Greedy-01
Navbatda kutish vaqti
Muallif:
Iqbolshoh Ilhomjonov
Oson
1000 ms
128 MB
20%
Bitta kassaga $n$ ta xaridor keldi; $i$-xaridorga xizmat ko'rsatish $t_{i}$ daqiqa davom etadi. Kassir xaridorlarni istalgan tartibda qabul qilishi mumkin. Har bir xaridor o'zidan oldingilarning hammasiga xizmat ko'rsatilguncha kutadi (birinchisi $0$ daqiqa kutadi). Barcha xaridorlarning kutish vaqtlari yig'indisi eng kichik bo'ladigan tartibni tanlab, shu yig'indini toping.
Kiruvchi ma'lumotlar
Birinchi qatorda natural son $n$. Ikkinchi qatorda bo'sh joy bilan ajratilgan $n$ ta natural son $t_{i}$.
Chiquvchi ma'lumotlar
Bitta butun son — eng kichik umumiy kutish vaqti.
Izoh
$1 \le n \le 10^{5}$
$1 \le t_{i} \le 10^{9}$
Misollar
Kirish #1
3 5 1 3
Chiqish #1
5
Kirish #2
4 2 2 2 2
Chiqish #2
12