소가 길을 건너간 이유 2020

농부 존의 목장에는 $y$좌표가 $0$보다 크고 $L$보다 작은 영역에 큰 길이 나 있다. 소들은 길가의 헛간에서 살며, 헛간마다 위치가 다르다. 길의 위쪽에 사는 소는 $N$마리이고, $i$번째 소는 $(U_i, L)$에 산다. 아래쪽에 사는 소는 $M$마리이고, $j$번째 소는 $(D_j, 0)$에 산다.

농부 존은 소들이 자꾸 길을 건너는 것이 못마땅해서 길에 구덩이를 파 소들이 건너지 못하게 했다. 길을 자주 건너던 소들은 항의했지만 그 항의는 받아들여지지 않았다.

어느 날 소들은 꿀벌에게 쏘이면 잠깐 동안 하늘을 날 수 있다는 사실을 알게 되었다. 이 소식이 퍼지자 소들은 다시 자유롭게 길을 건너기 시작했다. 소들은 하늘을 나는 것이 너무 좋아서, 굳이 건너지 않아도 되는 상황에서도 여러 번 건넜다.

하늘을 나는 동안에는 소가 방향을 조절할 수 없어서 공중에서 소들이 부딪히는 사고가 자주 일어났다. 이를 막기 위해 리더 베시는 다음 조건을 만족하는 항로를 만들려고 한다.

• 항로는 위쪽 헛간과 아래쪽 헛간을 잇는 선분이다.
• 항로는 $N+M-1$개만 만든다.
• 모든 헛간이 항로를 통해 연결되어야 한다.
• 임의의 두 항로는 헛간이 아닌 곳에서 교차하면 안 된다.

소는 한 번 날 때마다 비행 거리의 제곱만큼 힘이 든다. 여러 번 날면 비행 거리 제곱의 합만큼 힘이 든다. 베시는 두 헛간 사이의 거리를, 항로만 이용해 한 헛간에서 다른 헛간까지 갈 때 필요한 최소 힘으로 정의했다.

베시는 모든 헛간 쌍에 대한 거리의 합을 최소화하려고 한다. 베시를 도와 최적의 항로를 구하는 프로그램을 작성하라.

첫 번째 줄에 위쪽에 사는 소의 수 $N$, 아래쪽에 사는 소의 수 $M$, 길의 폭 $L$이 주어진다 ($1 \le N, M \le 3\ 000$, $1 \le L \le 30\ 000$).

두 번째 줄에는 위쪽 소들의 $x$좌표가 오름차순으로 주어진다.

세 번째 줄에는 아래쪽 소들의 $x$좌표가 오름차순으로 주어진다.

모든 좌표는 $0$ 이상 $30\ 000$ 이하의 정수이다.

베시가 최적의 항로를 구축했을 때, 모든 헛간 쌍에 대한 거리의 합을 출력한다.