Flu(インフルエンザ) - joi2008-day1

時間制限: 1秒

メモリ制限: 64MB

今年はJOI 国でインフルエンザの大流行の兆しがある．JOI 国にはn 個の都市P1, . . . , Pn があり，都市Pi の場所は座標を用いてPi(xi, yi) と表される．異なる都市が同じ座標を持つことはない．すなわち，i ≠ j であれば，(xi, yi) ≠ (xj , yj) である．また，都市P1 は首都のJOI 市である．

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

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

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

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

Input.

入力ファイルflu.in の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 行目) は都市P1, . . . , Pn の位置を表す．i + 4 行目(1 ≤ i ≤ n) には，2 つの整数xi, yi (0 ≤ xi, yi < 1, 000) が空白を区切りとして書かれており，都市Pi の座標がPi(xi, yi) であることを意味する．

Output.

出力は，標準出力に行うこと．JOI 市で流行が始まってからk 日後において，JOI 国内でインフルエンザが流行している都市の数を表す整数を1 行で出力せよ．採点基準採点に用いる入力データのうち，配点の20% 分はn ≤ 1000, k ≤ 50, 0 ≤ xi, yi < 100をみたす．また，これとは別の配点の30% 分はn ≤ 10000, 0 ≤ xi, yi < 1000 をみたす．

例

flu.in	標準出力
`9 2 2 3 1 3 3 3 2 2 3 1 0 0 0 3 0 5 3 5 5 5`	`4`

この入力例において，都市の数はn = 9 である．また，9 つの都市P1, . . . , P9 の座標は順にP1(1, 3), P2, P3, P4, P5, P6, P7, P8, P9で与えられる．インフルエンザの感染可能距離はd = 2 であり，各都市で流行が続く日数はm = 2 である．また，k = 3 である．

最初，インフルエンザが流行しているのはJOI 市P1 のみである．1 日後には，インフルエンザの流行は，P1 からの距離が2 以下の都市P2, P3, P6 に拡大する．また，JOI 市P1 における流行はまだ収まらない．2 日後には，流行はP4, P7, P8 に拡大し，JOI 市P1 における流行は収まる．3 日後には，流行はP9 に拡大し，P2, P3, P6 における流行は収まる．

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

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