Хорошие времена в библиотеке Хайди закончились. Читатели подключились к интернету и совсем перестали посещать библиотеку. Кроме этого в книжном магазине стали брать дополнительную плату за некоторые книги. А именно, если в предыдущих версиях каждая книга могла быть куплена за 1 CHF, теперь цена книги i составляет ci CHF.
В первой строке следуют два числа n и k (
).
Во второй строке следуют n целых чисел a1, a2, ..., an (1 ≤ ai ≤ n) — где ai равно номеру книги, которую хочет прочитать посетитель в i-й день.
В третьей строке следуют n целых чисел c1, c2, ..., cn (0 ≤ ci ≤ 106) – стоимости книг.
В единственной строке выведите минимальную стоимость покупки книг в книжном магазине, которые необходимы для удовлетворения запросов всех посетителей.
4 80
1 2 2 1
1 1 1 1
2
4 1
1 2 2 1
1 1 1 1
3
4 2
1 2 3 1
1 1 1 1
3
7 2
1 2 3 1 1 1 2
1 10 1 0 0 0 0
13
Первые три примера повторяются, но четвертый является новым.
В четвертом примере, покупая книгу 3, Хайди должна избавиться от книги 1 или от книги 2. Хотя книга 2 будет запрошена позже, чем книга 1, Хайди сохранит ее, потому что очень дорого покупать снова книгу 2.
