내가 생각한 최강의 이불

당신은 새 생활을 준비하며 이불을 $N$장 샀다. $i$번째 이불은 $s_i$의 온기 공급력을 가진다. 앞으로 $M$일간의 기온 예측으로부터 $j$번째 날에는 $d_j$의 온기 수요가 예상된다. 온기가 부족해도 너무 많아도 쾌적함이 떨어지므로, $j$번째 날 덮고 있는 이불의 온기 공급력 총합과 $d_j$의 차의 절댓값을 $j$번째 날의 불쾌도라고 부르기로 한다. 이 $M$일 동안의 불쾌도 합계를 최대한 줄이고 싶다.

그런데 당신의 방은 안타깝게도 매우 좁아서 침대와 벽장밖에 없다. 그래서 침대에 이불을 1장 늘리려면 그때 벽장 맨 위에 있는 이불을 침대 맨 위에 올리는 수밖에 없다. 반대로 침대의 이불을 1장 줄이려면 그때 침대 맨 위에 있는 이불을 벽장 맨 위에 놓는 수밖에 없다. 또한 하루에 움직일 수 있는 이불의 장수에는 제한이 없지만, 한 번에 1장씩만 움직일 수 있다.

이제 당신은 방금 사 온 이불을 벽장에 넣을 예정이다. 이때에 한해 이불을 원하는 순서로 벽장에 넣을 수 있다. 어떻게 이불을 벽장에 넣고, 그 뒤 날마다 어떻게 이불을 꺼내고 넣어야 쾌적하게 매일을 보낼 수 있을까. $M$일간의 불쾌도 합을 최소화할 때 그 합의 값을 구하라. 한 번도 사용되지 않는 이불이 있어도 되고, 이불을 한 장도 사용하지 않는 날이 있어도 된다.

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

N M
s1 s2 ... sN
d1 d2 ... dM

데이터 세트의 1번째 줄에는 이불의 장수 $N$과 기온이 예측된 일수 $M$을 나타내는 정수가 공백으로 구분되어 주어진다. 2번째 줄에는 $N$개의 정수 $s_1, s_2, \dots, s_N$이 공백으로 구분되어 주어지고, $s_i$는 $i$번째 이불의 온기 공급력을 나타낸다. 3번째 줄에는 $M$개의 정수 $d_1, d_2, \dots, d_M$이 공백으로 구분되어 주어지고, $d_j$는 $j$번째 날의 온기 수요를 나타낸다. 이 정수들은 $1 \le N \le 15$, $1 \le M \le 100$, $1 \le s_i, d_j \le 1{,}000{,}000$을 만족한다.

입력의 끝은 $N = M = 0$인 데이터 세트로 나타낸다. 이 데이터 세트에 대해서는 출력을 하지 않는다.

각 데이터 세트에 대해 $M$일간의 불쾌도 합의 최솟값을 1줄에 출력하라.

5번째 케이스에 대해서는 위에서부터 5, 2, 3, 1의 순서로 벽장에 넣고, 1일째에는 3장을 꺼내 $|10 - (5 + 2 + 3)| = 0$, 2일째에는 2장을 넣어 $|4 - 5| = 1$, 3일째에는 1장을 꺼내 $|7 - (5 + 2)| = 0$이므로 합계는 $0 + 1 + 0 = 1$이 된다.