A Taja le gusta ir a la cafetería «In the cube» con sus amigos, ya que tiene un sistema de pedidos muy conveniente. Para hacer un pedido, el cliente debe caminar hacia el puesto automatizado y elegir los platos que desee. Hay varios puestos de este tipo y todos están fijados en lugares específicos dentro de la cafetería.

En la cafetería, los clientes se sientan frente a las mesas; hay $k$ mesas. La mesa $i$-ésima no puede atender a más de $c_i$ personas. La incomodidad de la posición de una mesa es la suma de las distancias desde esta mesa hasta los $c_i$ puestos automatizados más cercanos a ella.

Formalmente, la cafetería es una cuadrícula $(0, 0) - (5000, 5000)$. Cada celda $(x, y)$ ($0 \le x, y \le 5000$) puede contener un puesto automatizado, una mesa o nada.

La distancia entre las celdas $(x_1, y_1)$ y $(x_2, y_2)$ es igual a $|x_2 - x_1| + |y_2 - y_1|$.

Debes organizar las mesas de tal manera que la suma total de las incomodidades de todas las mesas sea mínima.

Entrada

La primera línea de la entrada contiene dos enteros $n$ y $k$ ($1 \le n \le 18$, $1 \le k \le 200$), que representan la cantidad de puestos automatizados y mesas, respectivamente.

Las siguientes $n$ líneas contienen las coordenadas del puesto $i$-ésimo: dos enteros $x_i$ e $y_i$ ($0 \le x_i, y_i \le 5000$).

Las siguientes $k$ líneas contienen cada una un solo entero $c_j$ ($1 \le c_j \le n$), que representa el número de asientos en la mesa $j$-ésima.

Salida

La salida debe contener un solo entero: la incomodidad total mínima.

Ejemplos

Entrada 1

3 4
1 2
4 1
5 4
1
2
3
3

Salida 1

20

Entrada 2

2 10
0 0
5000 5000
1
1
1
1
1
1
1
1
1
1

Salida 2

16

Nota

Una posible disposición de las mesas para el primer ejemplo se ve así: