Ex - Explosive Chain Reaction

2 secs 1024 MB
uni_kakurenbo's icon uni_kakurenbo

問題文

xyx‐y 座標平面上に 11 から NN までの番号がついた NN 個の爆発物があり,爆発物 i(1iN)i \scriptsize \hspace{0.3em} (1 \leq i \leq N) の座標は (xi,yi)(x_i, y_i) です.

爆発物には,起爆装置がついているものとそうでないものがあることが分かっています.
長さ NN の文字列 SS について,爆発物 ii に起爆装置がついている場合は Si=S_i = Y,そうでない場合は SiS_i = N です.
ただし,文字列 SS の先頭の文字は S1S_1 であり,SiS_i は文字列 SSii 番目の文字を指します.

爆弾魔の MojaMoja 君は,時刻 00 で一斉に起爆装置を起動し,起爆装置がついている爆発物をすべて爆破させます.
また,時刻 tt で爆破された爆発物は,自身を中心とした半径 rr の円の内部(境界を含む)にある爆発物を時刻 t+1t+1 で爆破(誘爆)させます.

一度爆破された爆発物が再度爆破することはありません.

誘爆が起こらなくなるまで時間が経過したとき,NN 個の爆発物のうちいくつの爆発物が爆破されているか求めてください.

制約

  • 1N30001 \leq N \leq 3000
  • 0r1090 \leq r \leq 10^9 \hspace{0.2em}
  • 109xi,yi 109(1iN)-10^9 \leq x_i, y_i\ \leq 10^9 \scriptsize \hspace{0.4em} (1 \leq i \leq N)
  • N,r,xi,yi(1iN)N, r, x_i, y_i \scriptsize \hspace{0.4em} (1 \leq i \leq N) は整数
  • SSYN のみからなる長さ NN の文字列

入力

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

NrN \hspace{0.5em} r
x1y1x_1 \hspace{0.5em} y_1
x2y2x_2 \hspace{0.5em} y_2
\vdots
xNyNx_N \hspace{0.5em} y_N
SS

出力

答えを出力せよ.

サンプル

入力例1
6 4
1 -1
4 2
3 5
-5 2
4 -2
-3 -3
YNNNNN
出力例1
4

最終的に,爆発物 1,2,3,51, 2, 3, 544 つが爆破されます.
入力例1_爆発物配置図


入力例2
9 3
1 2
3 -2
-2 1
0 0
3 3
-3 -2
-5 1
-2 4
3 -2
NNNYNNNNN
出力例2
6

一つの爆発物が同時に複数の爆発物を誘爆させることもあり得ます.
また,複数の爆発物が同一の座標に重なっている場合もあります.
入力例1_爆発物配置図


入力例3
9 3
1 2
3 -2
-2 1
0 0
3 3
-3 -2
-5 1
-2 4
3 -2
NYNYNNNNN
出力例3
8

入力例 22 とは文字列 SS のみが異なります.
MojaMoja 君が最初に爆破させる爆発物は一つとは限りません.

提出


Go (1.21)