일직선 이더넷 배선

문제

알렉산드리아에 사는 유클리드는 사 모은 책이 너무 많아 서재가 비좁아지자 새 집을 사서 이사하기로 했다.

새 집에는 서재가 여러 개 있다. 그가 처음 할 일은 모든 서재를 인터넷에 연결하는 것이다. 그림 3처럼 서재는 모두 곧은 복도의 한쪽 벽을 따라 늘어서 있고, 각 서재에는 벽에 서재 내부로 이어지는 커넥터(그림의 ◦)가 하나씩 있다. 서재 내부 배선은 이미 끝냈으므로 이제 서재와 인터넷을 연결하면 된다. 인터넷으로 이어지는 커넥터는 복도 끝에 있는 하나(그림의 •)뿐이다.

그림 3: 복도와 서재

그는 예전 집에서 이더넷 케이블 몇 개와 포트가 충분한 허브를 넉넉히 가져왔다. 이것들로 모든 서재를 인터넷에 연결하려 한다. 그리고 그림 4처럼 케이블을 벽을 따라 일직선으로 깔려고 한다. 먼저 사용하는 허브 수를 최소로 하고, 그다음으로 케이블 여유 길이의 합을 최소로 하는 것이 목표이다.

그림 4: 벽을 따라 케이블 깔기

복도를 수직선의 구간 $[0, L]$ 로 보자. 인터넷 커넥터는 $x = 0$ 에, $i$ 번째 서재의 커넥터는 $x = x_i$ 에 있다. 배선 규칙은 다음과 같다.

케이블 하나는 두 지점(커넥터 또는 허브)을 잇는다. 두 지점 사이 거리가 $d$ 이고 케이블 길이가 $l$ 이면 $l \ge d$ 여야 하며, 이 케이블의 여유 길이는 $l - d$ 이다.
인터넷 커넥터와 각 서재 커넥터에는 케이블을 정확히 하나씩 연결한다. 케이블끼리는 허브에서만 이을 수 있다.
허브는 포트가 충분하고, 복도 안의 아무 위치(좌표 $0$ 이상 $L$ 이하)에나 둘 수 있다. 여러 허브를 같은 위치에 둘 수 있고 케이블이 겹쳐도 된다.
케이블을 모두 쓸 필요는 없지만 각 케이블은 한 번만 쓸 수 있다.
모든 서재 커넥터는 케이블과 허브를 거쳐 인터넷 커넥터와 연결되어야 한다.

주어진 상황마다 허브의 최소 개수와, 허브를 그만큼 쓸 때 케이블 여유 길이 합의 최솟값을 구하라. 허브의 크기와 케이블의 굵기는 무시한다.

입력

입력은 여러 데이터 세트로 이루어진다. 각 데이터 세트의 형식은 다음과 같다.

N M L
x1 x2 ... xN
l1 l2 ... lM

첫째 줄에 세 정수 $N$ , $M$ , $L$ 이 주어진다. $N$ ( $1 \le N \le 5$ )은 서재의 수, $M$ ( $1 \le M \le 10$ )은 케이블의 수, $L$ ( $1 \le L \le 20$ )은 복도의 길이이다. 둘째 줄에는 $N$ 개의 양의 정수가 증가하는 순서로 주어진다. $i$ 번째 정수 $x_i$ 는 $i$ 번째 서재 커넥터의 x좌표이며 $x_i \le L$ 이다. 셋째 줄에는 $M$ 개의 양의 정수가 감소하지 않는 순서로 주어진다. $i$ 번째 정수는 $i$ 번째 케이블의 길이이다. 길이가 $L$ 보다 긴 케이블은 없다.

입력의 끝은 0 세 개가 적힌 줄로 나타내며, 이 줄은 데이터 세트가 아니다.

출력

각 데이터 세트마다 한 줄에 두 정수를 공백 하나로 구분해 출력한다. 첫 번째 정수는 허브의 최소 개수이고, 두 번째 정수는 케이블 여유 길이 합의 최솟값이다.

가능한 배선이 없으면 대신 Impossible을 출력한다.