차분 펄스 부호 변조

차분 펄스 부호 변조는 주로 음성 신호를 압축할 때 쓰이는 압축 기법 중 하나이다.

음성 신호는 컴퓨터에서 정수열(임펄스열)로 다룬다. 정수열은 입력 신호를 일정한 시간 간격으로 표본화(샘플링)하고 진폭을 기록한 것이다. 일반적으로 이 정수열은 이웃한 값이 서로 가깝다는 경향이 있다. 이 점을 이용해 이웃한 값의 차분을 부호화하여 압축률을 높이는 것이 차분 펄스 부호 변조이다.

이 문제에서는 차분값을 미리 정해진 값의 집합에서 고르는 것을 생각한다. 이 값의 집합을 코드북이라고 부른다. 복호화한 음성 신호 yn은 다음 식으로 정해진다.

y**n = y**n - 1 + C[k**n]

여기서 k**n은 프로그램이 출력하는 출력 열이고, C[j]는 코드북의 j번째 값이다. 다만 y**n은 덧셈 결과가 0보다 작으면 0으로, 255보다 크면 255로 각각 반올림한다. 또 y0의 값은 128로 한다.

입력 신호와 코드북이 주어졌을 때, 원래 입력 신호와 복호화한 출력 신호의 차의 제곱합이 최소가 되도록 출력 열을 고르고, 그때의 차의 제곱합을 출력하는 프로그램을 작성하라.

예를 들어 코드북으로 {4, 2, 1, 0, -1, -2, -4}라는 값의 집합을 사용해 131, 137이라는 열을 압축하는 경우, y**0 = 128, y**1 = 128 + 4 = 132, y**2 = 132 + 4 = 136*이라는 열로 압축하면 제곱합이 (131 - 132)^2 + (137 - 136)^2 = 2로 최소가 된다.

또 코드북으로 마찬가지로 {4, 2, 1, 0, -1, -2, -4}라는 값의 집합을 사용해 131, 123이라는 열을 압축하는 경우, y**0 = 128, y**1 = 128 + 1 = 129, y**2 = 129 - 4 = 125*와 같이, 앞의 예와 달리 131에 더 가까워지는 +2를 택하지 않는 편이 (131 - 129)^2 + (123 - 125)^2 = 8이라는 더 작은 제곱합을 얻는다.

위 두 예는 sample 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를 만족한다.

데이터 세트 안의 입력 항목은 모두 정수이다. 입력의 끝은 공백 문자 하나로 구분된 두 개의 0으로만 이루어진 줄로 나타낸다.

각 데이터 세트에 대해 원래 입력 신호와 복호화한 출력 신호의 차의 제곱합의 최솟값을 한 줄에 출력하라.