The Most Powerful Bed

時間制限 : 8 sec, メモリ制限 : 524288 KB

ぼくのかんがえたさいきょうのおふとん

あなたは新生活に備え,おふとんを N 枚買った. i 番目のおふとんは si のぬくもり供給力をもつ. これから M 日間の気温の予測から,j 日目には dj のぬくもり需要が予想される. ぬくもりが足りなくても多すぎても快適さが損なわれるので,j 日目に掛けているおふとんのぬくもり供給力の総和と dj の差の絶対値を j 日目の不快度と呼ぶことにする. このM 日分の不快度の合計ができるだけ少なくなるようにしたい.

ところで,あなたの部屋は残念ながらとても狭く,ベッドと押入れしかない. そのため,ベッドにおふとんを 1 枚増やすには,そのとき押入れの一番上にあるおふとんをベッドの一番上に乗せるしかない. 逆に,ベッドのおふとんを 1 枚減らすには,そのときベッドの一番上にあるおふとんを押入れの一番上に置くしかない. また,1 日に動かせるおふとんの枚数に制限は無いが,一度に 1 枚ずつしか動かすことができない.

さて,あなたはこれから買ってきたおふとんを押入れにしまう予定である. このときに限り,おふとんを好きな順序で押入れにしまうことができる. どのようにおふとんを押入れに収納し,その後,日々どのようにおふとんを出し入れすれば,快適に毎日を過ごせるだろうか. M 日間の不快度の和を最小化するとき,その和の値を求めよ. なお,一度も使われないおふとんがあってもよく,おふとんを一枚も使わない日があってもよい.

Input

入力は複数のデータセットからなる. 各データセットは以下の形式である.

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

データセットの 1 行目には,おふとんの枚数 N と,気温が予測されている日数 M を表す整数がスペース区切りで与えられる. 2 行目には N 個の整数 s1, s2, ..., sN がスペース区切りで与えられ,sii 番のおふとんのぬくもり供給力を表す. 3 行目には M 個の整数 d1, d2, ..., dM がスペース区切りで与えられ,djj 日目のぬくもり需要を表す. これらの整数は,1 ≤ N ≤ 15, 1≤ M ≤ 100, 1 ≤ si, dj ≤ 1,000,000 を満たす.

入力の終わりは N = M = 0 のデータセットで表される. このデータセットについて出力を行ってはならない.

Output

各データセットについて,M 日間の不快度の和の最小値を 1 行に出力せよ.

Sample Input

1 1
5
6
1 1
5
2
1 1
20
5
4 1
2 4 5 9
8
4 3
3 5 2 1
10 4 7
5 5
2 2 2 2 2
1 3 5 7 9
2 5
2 5
2 5 2 5 2
0 0

Output for Sample Input

1
2
5
1
1
5
4

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 となる.


Source: ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2016 , Japan, 2016-06-12
http://acm-icpc.aitea.net/