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$ 行には、$j$ 番目のテーブルの座席数 $c_j$ ($1 \le c_j \le n$) が含まれます。

出力

最小の合計不快感を表す整数を1つ出力してください。

入出力例

入力 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