Різнобарвний кістяк#12881

Різнобарвний кістяк

2 секунди
256 мегабайтів
Складна

В нас є граф на вершинах. -та вершина має колір c_i і значення a_i. Якщо вершини та різного кольору, то між ними є ребро ваги |a_i-a_j|, інакше між ними немає ребра. Гарантується, що є хоча б два різні кольори.

Знайдіть вагу мінімального кістяка в цьому графі.

Нагадаємо, що кістяк графу  — це підмножина з n-1 ребер цього графу, що формують дерево. Мінімальний кістяк  — це кістяк з найменшою сумою ваг ребер в ньому.

Вхідні дані

Перший рядок вхідних даних містить єдине ціле число (2 \le n \le 2\cdot 10^5)  — кількість вершин в графі.

Другий рядок вхідних даних містить цілих чисел c_1, c_2, \ldots, c_n (1 \le c_i \le n)  — кольори вершин графу. Гарантується, що серед c_1, c_2, \ldots, c_n є принаймні два різні кольори.

Третій рядок вхідних даних містить цілих чисел a_1, a_2, \ldots, a_n (0 \le a_i \le 10^9).

Вихідні дані

Виведіть єдине число  — вагу мінімального кістяку цього графу.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

В першому прикладі, мінімальний кістяк формують ребра (1, 3), (3, 4), (4, 2), кожне з вагою .

В другому прикладі, один з мінімальних кістяків формують ребра (5, 6), (5, 4), (5, 2), (6, 3), (6, 1) з вагами 96, 97, 98, 97, 98 відповідно. Вага всього кістяка рівна 96 + 97 + 98 + 97 + 98 = 486.