Heidi and Library (어려움)

Heidi의 도서관에서 좋았던 시절은 끝났다. 마멋들은 마침내 인터넷에 연결할 수 있게 되었고 도서관에 아예 오지 않게 되었다. 그뿐만 아니라 서점은 일부 책에 터무니없이 비싼 가격을 매기기 시작했다. 즉, 이전 버전에서는 각 책을 1 CHF에 살 수 있었지만, 이제 책 i의 가격은 ci CHF이다.

입력의 첫째 줄에 두 정수 n와 k ()가 주어진다. 둘째 줄에는 책 요청의 순서인 n개의 정수 a1, a2, ..., an (1 ≤ ai ≤ n)이 주어진다. 셋째 줄에는 책의 가격인 n개의 정수 c1, c2, ..., cn (0 ≤ ci ≤ 106)이 주어진다.

모든 요청을 충족하기 위해 서점에서 책을 사는 데 드는 최소 비용을 한 줄에 출력한다.

처음 세 예제는 반복해서 제시된 것이지만, 네 번째 예제는 새롭다.

네 번째 테스트 케이스에서 책 3을 살 때 Heidi는 책 1 또는 2 중 하나를 버려야 한다. 책 2이 책 1보다 나중에 요청되더라도, 다시 사기에는 매우 비싸므로 그 책을 보관해야 한다.