Differential Pulse Code Modulation

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

Problem C: Differential Pulse Code Modulation

差分パルス符号変調は主に音声信号を圧縮する際に用いられる圧縮手法の一つである.

音声信号は計算機上では整数列(インパルス列)として扱われる.整数列は入力信号を一定時間間隔で標本化(サンプリング)し,振幅を記録したものである.一般にこの整数列は前後の値が近いという傾向がある.これを利用し,前後の値の差分を符号化し,圧縮率を向上させるのが差分パルス符号変調である.

本問題では差分の値をあらかじめ定められた値の集合から選ぶことを考える.この値の集合をコードブックと呼ぶことにする.復号化後の音声信号 yn は以下の式で定められる.

yn = yn - 1 + C[kn]

ここで kn はプログラムによって出力される出力系列, C[j] はコードブックの j 番目の値である.ただし yn は加算によって0未満の値となった場合は0に,255より大きい値となった場合は255にそれぞれ丸められる.また, y0 の値は128とする.

あなたの仕事は,入力信号とコードブックが与えられたときに,元の入力信号と復号化後の出力信号との差の二乗和が最小となるように出力系列を選んで,そのときの差の二乗和を出力するプログラムを書くことである.

例えば,コードブックとして {4, 2, 1, 0, -1, -2, -4} という値のセットを使って 131, 137 という列を圧縮する場合, y0 = 128, y1 = 128 + 4 = 132, y2 = 132 + 4 = 136 という列に圧縮すると 二乗和が (131 - 132)^2 + (137 - 136)^2 = 2 と最小になる.

また,同じくコードブックとして {4, 2, 1, 0, -1, -2, -4} という値のセットを使って 131, 123 という列を圧縮する場合, y0 = 128, y1 = 128 + 1 = 129, y2 = 129 - 4 = 125 と,先程の例とは違って 131 により近づく +2 を採用しない方が (131 - 129) ^ 2 + (123 - 125) ^ 2 = 8 というより小さな二乗和が得られる.

上記 2つの例は sample input の最初の 2例である.

Input

入力は複数のデータセットから構成される.各データセットの形式は次に示すとおりである.

N M
C1
C2
...
CM
x1
x2
...
xN

最初の行は,入力データセットの大きさを規定する. N は圧縮する入力信号の長さ(サンプル数)である. M はコードブックに含まれる値の個数である. N 及び M は1 ≤ N ≤ 20000,1 ≤ M ≤ 16を満たす.

これに続く M 行は,コードブックの記述である. Ci はコードブックに含まれる i 番目の値を表す. Ci は-255 ≤ Ci ≤ 255を満たす.

これに続く N 行は,入力信号の記述である. xi は入力信号を表す整数列の i 番目の値である. xi は0 ≤ xi ≤ 255を満たす.

データセットの中の入力項目は,すべて整数である.入力の終りは,空白文字1個で区切られた2個のゼロのみからなる行で表される.

Output

入力の各データセットに対して, 元の入力信号と復号化後の出力信号との差の二乗和の最小値を一行で出力せよ.

Sample Input

2 7
4
2
1
0
-1
-2
-4
131
137
2 7
4
2
1
0
-1
-2
-4
131
123
10 7
-4
-2
-1
0
1
2
4
132
134
135
134
132
128
124
122
121
122
5 1
255
0
0
0
0
0
4 1
0
255
0
255
0
0 0

Output for the Sample Input

2
8
0
325125
65026

Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2010, 2010-06-27
http://acm-icpc.aitea.net/