음식 주문

Anthony와 그의 친구 $n$명은 식당에서 음식을 주문하려 한다. 메뉴에는 요리 $m$개가 있으며, 모든 친구는 처음에 자신이 먹고 싶은 요리를 골랐다. 하지만 Anthony는 일행이 서로 다른 요리를 많이 주문할수록 식당에서 제공하는 음식을 더 다양하게 볼 수 있어서 더 기쁘다. 그는 주문되는 서로 다른 요리의 수를 늘리기 위해 친구들의 음식값까지 대신 내줄 의향이 있다.

오늘 Anthony는 친구들이 적어도 $k$개의 서로 다른 요리를 주문하기를 바란다. 그는 친구가 원래 고른 요리의 가격과 더 비싼 요리의 가격 차액을 지불하여 그 친구의 주문을 더 비싼 요리로 바꾸게 할 수 있다. 단, 각 사람은 여전히 하나의 요리만 주문한다. 이러한 변경은 원하는 만큼 할 수 있다.

요리의 수와 각 요리의 가격, 친구들이 처음에 주문한 요리가 주어질 때, 친구들이 적어도 $k$개의 서로 다른 요리를 주문하도록 하기 위해 Anthony가 지불해야 하는 최소 금액은 얼마인가?

점수

여러 테스트 케이스 그룹으로 풀이를 평가한다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ | $10$ | 처음에는 모두 같은 요리를 사고 싶어 한다.

$2$ | $20$ | $k = n$

$3$ | $16$ | $n, m \le 15$

$4$ | $23$ | 모든 $1 \leq i \leq m$에 대해 $c_i = i$, 즉 요리의 가격은 $1, 2, 3, \dots, m$

$5$ | $31$ | 추가 제한 없음

첫째 줄에 친구의 수, 요리의 수, 원하는 서로 다른 주문의 수를 나타내는 세 정수 $n$, $m$, $k$가 주어진다. ($1 \leq n, m \leq 2 \cdot 10^5$, $1 \le k \le min(n, m)$)

다음 줄에는 정수 $x_1 \dots x_n$가 $n$개 주어지며, $x_i$ ($1 \leq x_i \leq m$)는 친구 $i$가 처음에 사고 싶어 하는 요리를 나타낸다.

다음 줄에는 정수 $c_1 \dots c_m$가 $m$개 주어지며, $c_i$ ($1 \leq c_i \leq 10^9$)는 요리 $i$의 가격을 나타낸다.

친구들이 적어도 $k$개의 서로 다른 요리를 주문하게 하기 위해 Anthony가 지불해야 하는 최소 금액을 정수로 출력한다. 불가능하다면 $-1$을 출력한다. 답이 반드시 $32$비트 정수 범위에 들어가지는 않는다는 점에 유의한다.

첫 번째 예제에서 Anthony는 친구 $1$가 첫 번째 요리에서 세 번째 요리로 바꾸도록 $2$크로나를 지불할 수 있다. 그러면 요리 $1$, 요리 $2$, 요리 $3$로, 서로 다른 요리 $3$개가 주문된다.

두 번째 예제에는 가격이 모두 $10$크로나인 요리가 두 개 있으며, 두 친구 모두 첫 번째 요리를 골랐다. 첫 번째 요리보다 비싼 요리가 없으므로 Anthony는 친구들의 선택을 바꾸기 위해 아무것도 할 수 없으며, 서로 다른 요리 $2$개를 결코 달성할 수 없다. 따라서 답은 $-1$이다.

세 번째 예제에서는 친구들이 이미 서로 다른 요리 두 개를 원하므로 Anthony는 아무것도 지불할 필요가 없다.

마지막 예제에서 Anthony는 친구 $8$명 모두가 서로 다른 요리를 주문하게 하려 한다. 여기서 가장 저렴한 방법은 친구 $3$, $4$, $7$, $8$가 $1\,000\,000\,000$크로나짜리 요리 중 하나로 주문을 변경하도록 비용을 지불하는 것이다. 총비용은 $3\,999\,999\,990$크로나이다.