Taja 喜欢和朋友们去“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$ 行包含每个售货台的坐标：两个整数 $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

说明

第一个样例中，一种可能的桌子摆放方式如下：