쉴드 생성기

일직선 상에 보호해야 하는 유닛 $N$개의 위치와 쉴드 생성기를 설치할 수 있는 $M$개의 후보지가 있다. 일직선 상의 위치는 자연수 좌표로 표시된다고 한다.

위치 $X$에 있는 특정한 후보지에 쉴드 생성기를 설치하고 그 범위를 $R$로 설정하면 범위 $[X-R, X+R]$에 있는 유닛을 모두 보호할 수 있다. 범위의 끝에 있는 유닛도 보호된다. 서로 다른 쉴드 생성기의 범위가 겹치는 것이 허용된다.

당신은 후보지들 중 $K$개를 선택하여 쉴드 생성기를 설치할 수 있다. 각 쉴드 생성기의 범위는 다르게 설정할 수 있다고 한다.

모든 유닛들을 보호하기 위해서 $K$개의 쉴드 생성기를 설치하고 그 범위들의 합을 최소화하는 프로그램을 작성하라.

입력 형식

첫째 줄에 후보지의 개수 $M$, 유닛의 개수 $N$, 설치할 수 있는 쉴드 생성기의 개수 $K$가 주어진다. ($1 \le M, N, K \le 500$, $K \le M$)

다음 줄에 후보지의 위치들이 $M$개의 정수로 주어진다.

그 다음 줄에 유닛의 위치들이 $N$개의 정수로 주어진다. 후보지들의 위치는 모두 다르고, 유닛들의 위치도 모두 다르다. 후보지와 유닛이 같은 위치에 있는 경우도 없다. 주어지는 위치는 모두 $1$ 이상 $10^9$ 이하이다.

출력 형식

$K$개의 쉴드 생성기를 설치했을 때 가능한 최소의 범위 합을 정수로 출력한다.

예제 1

4 3 1
20 50 55 73
17 23 46

26

예제 2

4 3 2
20 50 55 73
17 23 46

7

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설