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