24141번 - インフルエンザ (Flu) 다국어

今年は JOI 国でインフルエンザの大流行の兆しがある．JOI 国には n 個の都市 P₁, . . . , P_n が あり，都市 P_i の場所は座標を用いて P_i(x_i, y_i) と表される．異なる都市が同じ座標を持つことは ない．すなわち，i ̸= j であれば，(x_i , y_i) ≠ (x_j, y_j) である．また，都市 P₁ は首都の JOI 市で ある．

今年のインフルエンザは特別な型であり，次のような特徴がある．

1. 各都市において，インフルエンザの流行はちょうど m 日間続く．すなわち，もし都市 P_i でインフルエンザの流行が始まったとすると，P_i におけるインフルエンザの流行はちょう ど m 日間続き，m 日後にはインフルエンザの流行は収まる．
2. ある都市で一度インフルエンザが流行すると，その都市の市民の体内に抗体ができる．そ のため，インフルエンザが 1 つの都市で 2 回以上流行することはない．
3. インフルエンザは日を追うごとに都市から都市へと流行を拡大する．その感染可能距離 は d である．もし，都市 Pi でインフルエンザの流行が始まったとする．都市 Pj と Pi の 距離が d 以下であり，まだ Pj ではインフルエンザは流行していない場合，その翌日に は，都市 Pj でインフルエンザの流行が始まる．（都市 P_i(x_i, y_i) と P_j(x_j, y_j) の間の距離は √((x_i - x_j)² + (y_i - y_j)²) である．）
4. 上に述べた以外の経路でインフルエンザの流行が拡大することはない．

また，各 i = 1, . . . , n に対し，都市 Pi からの距離が d 以下であるような P_i 以外の都市の数は 10 個以下である．

ある日，インフルエンザの流行が，JOI 市 P1 で始まった．JOI 市以外の都市では，今年は， まだインフルエンザは流行していない．JOI 国では，治療に必要なワクチンを効率よく手配す るため，インフルエンザの流行状況を予測することにした．

入力として，都市の数 n，1 つの都市でインフルエンザの流行が続く日数 m，インフルエンザ の感染可能距離 d，整数 k ≥ 1，各都市の座標が与えられたとき，JOI 市で流行が始まってから k 日後において，JOI 国内でインフルエンザが流行している都市の数を求めるプログラムを作成 せよ．

入力の 1 行目には，JOI 国の都市の数 n (1 ≤ n ≤ 100, 000) が書か れている．2 行目には，各都市で流行が続く日数 m (1 ≤ m ≤ 100) が書かれている．3 行目に は感染可能距離 d (1 ≤ d ≤ 25) が書かれている．4 行目には整数 k (1 ≤ k ≤ 100) が書かれて いる．続く n 行 (5 行目～n + 4 行目) は都市 P₁, . . . , P_n の位置を表す．i + 4 行目 (1 ≤ i ≤ n) に は，2 つの整数 x_i, y_i (0 ≤ x_i, y_i < 1, 000) が空白を区切りとして書かれており，都市 P_i の座標 が P_i(x_i, y_i) であることを意味する．

出力は，標準出力に行うこと．JOI 市で流行が始まってから k 日後において，JOI 国 内でインフルエンザが流行している都市の数を表す整数を 1 行で出力せよ．

この入力例において，都市の数は n = 9 である．また，9 つの都市 P₁, . . . , P₉ の座標は順に

P₁(1, 3), P₂(3, 3), P₃(2, 2), P₄(3, 1), P₅(0, 0), P₆(0, 3), P₇(0, 5), P₈(3, 5), P₉(5, 5)

で与えられる．インフルエンザの感染可能距離は d = 2 であり，各都市で流行が続く日数は m = 2 である．また，k = 3 である．

最初，インフルエンザが流行しているのは JOI 市 P₁ のみである．1 日後には，インフルエン ザの流行は，P₁ からの距離が 2 以下の都市 P₂, P₃, P₆ に拡大する．また，JOI 市 P₁ における 流行はまだ収まらない．2 日後には，流行は P₄, P₇, P₈ に拡大し，JOI 市 P₁ における流行は収 まる．3 日後には，流行は P₉ に拡大し，P₂, P₃, P₆ における流行は収まる．

したがって，JOI 市で流行が始まってから 3 日後において，インフルエンザが流行している 都市は P₄, P₇, P₈, P₉ の 4 つであるから，4 を出力すればよい．

この入力例では，都市 P₅ においてインフルエンザが流行することはない．