레이지랜드
면접 대비시간 제한2초메모리 제한512 MB
n명의 일꾼이 k개 직업 중 하나를 고르고 재배정 비용이 b_i입니다. 직업마다 한 명만 남기고 남는 사람 중 가장 값싼 사람을 빈 직업에 보내 모든 직업을 채울 때의 최소 비용을 구합니다.
문제
레이지랜드 왕국에는 n명의 게으름뱅이가 살고 있다. 이들은 엄청나게 게으르며, 통치자인 위대한 레이지랜드 왕에게 많은 골칫거리를 만든다.
오늘 왕국을 위해 k개의 중요한 일을 해야 한다 (k ≤ n). 모든 일은 한 사람이 해야 하고, 각 사람은 최대 한 개의 일만 할 수 있다. 왕은 게으름뱅이들이 원하는 일을 하나씩 고르도록 허락했고, i번째 게으름뱅이는 일 ai를 골랐다.
아쉽게도 어떤 일은 아무도 고르지 않을 수 있으므로, 왕은 몇몇 게으름뱅이를 설득해 다른 일을 고르게 해야 한다. 왕은 i번째 게으름뱅이를 설득하는 데 bi분이 걸린다는 것을 알고 있다. 그는 노동부 장관에게 모든 일을 끝내기 위해 게으름뱅이를 설득하는 데 필요한 최소 총 시간을 계산해 달라고 부탁했다. 도와줄 수 있는가?
입력
첫째 줄에는 정수 n과 k가 주어진다 (1 ≤ k ≤ n ≤ 105). n은 게으름뱅이의 수, k는 일의 수이다.
둘째 줄에는 n개의 정수 a1, a2, ..., an이 주어진다 (1 ≤ ai ≤ k). 각 게으름뱅이가 고른 일이다.
셋째 줄에는 n개의 정수 b1, b2, ..., bn이 주어진다 (1 ≤ bi ≤ 109). i번째 게으름뱅이를 설득하는 데 왕이 써야 하는 시간이다.
출력
유일한 줄에 하나의 수를 출력한다. 모든 일을 끝내기 위해 게으름뱅이를 설득하는 데 필요한 최소 총 시간이다.
힌트
첫 번째 예시에서 최적의 계획은 게으름뱅이 1, 6, 8을 설득해 일 2, 4, 6을 하게 하는 것이다.
두 번째 예시에서는 모든 일을 누군가 골랐으므로 아무도 설득할 필요가 없다.