C. Los ogros tienen capas
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Chatito es un gato muy inteligente que se toma las películas muy en serio. Un día, mientras analizaba la obra maestra Shrek, escuchó la famosa frase de Shrek a Burro:

"¡Los ogros son como las cebollas. Tienen capas!"

Chatito pausó la película. Sus ojos se abrieron de par en par. ¡Acababa de tener una revelación! ¡Las películas también tienen capas!

Él cree que el arco narrativo de un personaje no es una sola cosa, sino una secuencia de N "momentos". Ha medido la "vibra" de cada momento, dándote una lista de N números: A.

Su gran teoría es que la película está dividida en exactamente K "capas" (segmentos) emocionales. (Por ejemplo, la "capa de la ira", la "capa de la negación", la "capa de la amistad", etc.).

Chatito, en sus estudios de cine, ha identificado K "emociones puras". Cada emoción tiene un "puntaje de vibra perfecto" (un "target"). Estos son K números en una lista T.

Para que su reseña de 5 estrellas sea correcta, Chatito debe:

1. Partir la película (la secuencia A) en K segmentos contiguos.

2. A cada segmento, debe asignarle una de las K emociones puras.

¡No puede repetir emociones! Cada una de las K emociones debe usarse exactamente una vez.

Chatito necesita medir qué tan "mal" encaja una emoción en un segmento. A esto le llama el "costo de cringe". Lo calcula así:

(a - b)2

donde;

a = Suma de la vibra del segmento

b = Vibra Perfecta de la Emocion

¡Ayuda a Chatito a encontrar la forma de partir la película que le dé el mínimo costo de cringe total!

Input

La primera línea contiene dos enteros N y K (1 ≤ K ≤ 10; K ≤ N ≤ 100) — el número de 'momentos' en la película y el número de 'capas' emocionales.

La segunda línea contiene N enteros A1, A2, ..., AN (1 ≤ Ai ≤ 105) — la lista A de las 'vibras' de cada momento.

La tercera línea contiene K enteros T0, T1, ..., TK - 1 (1 ≤ Tp ≤ 107) — la lista T de las 'vibras perfectas' para cada una de las K emociones.

Output

Imprime un solo número: el mínimo "costo de cringe" total que Chatito puede lograr.

Examples
Input
2 2
5 10
12 4
Output
5
Input
5 3
1 2 3 4 5
5 4 3
Output
3
Input
9 5
1 1 2 3 5 8 13 21 34
2 3 5 7 11
Output
906
Note

En el primer caso de ejemplo, la partición óptima es .

- El segmento [5] se asigna a la 'vibra perfecta' 4.

- El segmento [10] se asigna a la 'vibra perfecta' 12.

El costo total es (5 - 4)2 + (10 - 12)2 = 12 + ( - 2)2 = 1 + 4 = 5. Se puede probar que este es el mínimo costo posible.

En el segundo caso de ejemplo, la partición óptima es . La asignación óptima de vibras (5, 4, 3) es:

- El segmento [1, 2, 3] (Suma 6) -> 'vibra' 5. Costo: (6 - 5)2 = 1

- El segmento [4] (Suma 4) -> 'vibra' 3. Costo: (4 - 3)2 = 1

- El segmento [5] (Suma 5) -> 'vibra' 4. Costo: (5 - 4)2 = 1

El costo total es 1 + 1 + 1 = 3. Se puede probar que este es el mínimo costo posible.