004 - 山田之国

問題

山田之国には東西方向にまっすぐに伸びる $10^9$ 本の道路と、南北方向にまっすぐに伸びる $10^9$ 本の道路があります。
西から $X$ $(1 \leq X \leq 10^9)$ 番目、北から $Y$ $(1 \leq Y \leq 10^9)$ 番目の道路との交差点を $(X,Y)$ と表します。
交差点 $(X,Y)$ からは、もし交差点 $(X-1,Y),(X+1,Y),(X,Y-1),(X,Y+1)$ があるならば、それらの交差点へ $1$ 本の道を使って行くことができます。

ここで、交差点 $(X,Y)$ と 交差点 $(X',Y')$ との距離を、交差点 $(X,Y)$ から交差点 $(X',Y')$ に辿り着くために通らなければならない道の本数の最小値と定義します。

山田之国には $N$ 個の観光スポットがあり、$i$ $(1 \leq i \leq N)$ 番目の観光スポットは交差点 $(x_i, y_i)$ にあります。

山本君はこの山田之国で以下のように $Q$ 回の移動を行いました。

始め、山本君は交差点 $(1,1)$ にいる。
$j$ $(1 \leq j \leq Q)$ 回目の移動では、$N$ 個ある観光スポットのなかで、 現在いる交差点との距離が、$1$ 以上かつ $k_j$ との差の絶対値が最小である観光スポットがある交差点に移動する。
ただし、そのような観光スポットが複数存在する場合は交差点 $(1,1)$ に移動する。

山本君が必ず最短距離で移動したとき、山本君が通った道の本数を求めて下さい。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$
$k_1$
$k_2$
$\vdots$
$k_Q$

出力

山本君の通った道の本数を出力せよ。
出力の末尾には改行を入れること。

制約

• $2 \leq N \leq 1000$
• $1 \leq Q \leq 1000$
• $1 \leq x_i, y_i \leq 10^9$
• $(x_i,y_i) \neq (1,1)$
• $1 \leq k_j \leq 10^{10}$
• 複数の観光スポットが同じ交差点に存在することはない
• 入力は全て整数である

入出力例１

入力例１

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

出力例１

8

$(1,1) \to (1,1) \to (2,2) \to (2,8)$ というように移動します。
例として、$1$ 回目の移動のときの交差点 $(1,1)$ からの各観光スポットのある交差点への距離は以下の通りです。

• $(2,2): \ 2$
• $(4,1): \ 3$
• $(2,8): \ 8$
• $(2,3): \ 3$
• $(5,1): \ 4$

このとき、距離と $3$ の差の絶対値が最小である観光スポットは $2,4$ 番目の観光スポットです。$3$ との差の絶対値が最小である観光スポットが $2$ つ存在しているため、山本君は交差点 $(1,1)$ に移動します。交差点 $(1,1)$ から交差点 $(1,1)$ に移動するため、通る道の本数は $0$ 本です。

入力例２

20 10
93 74
85 26
95 47
85 5
23 40
59 87
6 22
69 72
50 5
27 56
10 30
73 24
41 73
13 39
42 52
34 34
23 86
57 64
56 11
2 88
73
112
70
131
92
15
106
188
180
8

出力例２

881