소가 길을 건너간 이유 2020

농부 존의 목장에는 $y$좌표가 $0$보다 크고 $L$보다 작은 영역에 커다란 길이 나있다. 소들은 길가에 있는 헛간에서 살고 있으며 서로 다른 곳에 살고 있다. 길의 위쪽에 살고 있는 소들은 총 $N$마리이며 $i$번째 소는 $\left(U\_i, L\right)$에 살고 있다. 길의 아래쪽에 살고 있는 소들은 총 $M$마리이며 $j$번째 소는 $\left(D\_j, 0\right)$에 살고 있다.

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

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

하늘을 나는 동안에는 소들이 방향을 조절할 수 없기 때문에 소들이 공중에서 부딪히는 사고가 종종 발생했다. 사고가 나지 않기 위해 소들의 리더 베시는 아래 조건을 만족하도록 항로를 만들어서 사고가 일어나지 않도록 하려고 한다.

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

소들은 한번 날 때 비행 거리의 제곱만큼 힘이 든다. 만약 소가 여러 번 난다면 비행 거리의 제곱의 합만큼 힘이 든다. 이에 따라 베시는 두 헛간 사이의 거리를 ‘항로만 이용하여 한 헛간에서 다른 헛간까지 갈 때 필요한 최소 힘’으로 정의했다.

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

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

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

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

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

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