Тая любит ходить в кафе «In the cube» со своими друзьями, так как там очень удобная система заказа. Чтобы сделать заказ, гость должен подойти к автоматизированной стойке и выбрать любые блюда, которые ему нравятся. В кафе есть несколько таких стоек, и все они закреплены в определенных местах.

В кафе гости сидят за столами, всего имеется $k$ столов. $i$-й стол может обслужить не более $c_i$ человек. Неудобство расположения стола равно сумме расстояний от этого стола до $c_i$ ближайших к нему автоматизированных стоек.

Формально, кафе представляет собой сетку $(0, 0) - (5000, 5000)$. Каждая ячейка $(x, y)$ ($0 \le x, y \le 5000$) может содержать либо одну автоматизированную стойку, либо один стол, либо быть пустой.

Расстояние между ячейками $(x_1, y_1)$ и $(x_2, y_2)$ равно $|x_2 - x_1| + |y_2 - y_1|$.

Вам необходимо расставить столы таким образом, чтобы общая сумма неудобств для всех столов была минимальной.

Входные данные

Первая строка входных данных содержит два целых числа $n$ и $k$ ($1 \le n \le 18$, $1 \le k \le 200$) — количество автоматизированных стоек и столов соответственно.

Следующие $n$ строк содержат координаты $i$-й стойки: два целых числа $x_i$ и $y_i$ ($0 \le x_i, y_i \le 5000$).

Далее следуют $k$ строк, каждая из которых содержит одно целое число $c_j$ ($1 \le c_j \le n$) — количество мест за $j$-м столом.

Выходные данные

Выведите одно целое число — минимальную общую сумму неудобств.

Примеры

Входные данные 1

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

Выходные данные 1

20

Входные данные 2

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

Выходные данные 2

16

Примечание

Возможное расположение столов для первого примера выглядит так: