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$ 行包含第 $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

說明

第一個範例中，桌子的一種可能安排方式如下：