Рекомендации новостей ВКонтакте ежедневно подбирают для каждого пользователя интересные публикации из \(n\) категорий. Каждая публикация принадлежит ровно к одной категории. Алгоритм массовых рекомендаций позволяет подобрать \(a_i\) новостей \(i\)-й категории.
Результаты последнего A/B теста показали, что пользователи активнее читают рекомендованные новости, если ни в каких двух категориях не рекомендовано одинаковое количество новостей. Алгоритм одиночного поиска рекомендуемой новости конкретной категории позволяет найти одну новость категории \(i\) за \(t_i\) секунд. Сколько минимально суммарно времени понадобится для того, чтобы добавить новости к уже сформированным алгоритмом массовых рекомендаций публикациям так, чтобы ни в каких двух категориях не было равное количество новостей? Уже подготовленные рекомендации нельзя исключить из предлагаемых пользователю.
Выходные данные
Выведите одно целое число — минимальное суммарное время работы алгоритма одиночного поиска.
Примечание
В первом тестовом примере можно добавить три публикации второго типа, на поиск которых уйдет 6 секунд.
Во втором тестовом примере все категории новостей уже содержат разное количество публикаций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 7 9 7 8
5 2 5 7 5
|
6
|
|
2
|
5
1 2 3 4 5
1 1 1 1 1
|
0
|