Hide

Problem E
森林火災

Languages en ja sv

整数の森で火事が発生した! 整数の森は無限の二次元平面で構成されており、整数の座標を持つ各点に木が生えています。 現在、これらの木のうち$N$本が燃えています。 1分ごとに、燃えている木から4つの隣の木(すぐ北、東、西、南の木)に火が燃え広がっていきます。 延焼を喰いとめるために、消防隊員が$M$本の木を切り倒しました。 切り倒された木は火をつけられないので、これらの点が炎に対する壁のような役割を果たしています。 あなたは、火事がどのような被害をもたらすかに興味があります。 $T$分後には大雨が降ってきて、火事は収まります。 したがって、あなたは、$T$分後に何本の木が燃えているかを知りたいのです。

入力

1行目には3つの整数が与えられます。

  • 燃えている木の数$N$ ($1 \leq N \leq 100$),

  • 切り倒した木の数$M$ ($0 \leq M \leq 100$),

  • 大雨が降るまでの時間(分) $T$ ($0 \leq T \leq 10^9$).

次の$N$行には2つの整数 $x_ i,y_ i$ ($0 \leq x_ i, y_ i < 10^5$)が与えられます。燃えている木の座標を表します。

次の$M$行には2つの整数 $x_ i,y_ i$ ($0 \leq x_ i, y_ i < 10^5$)が与えられます。切り倒した木の座標を表します。

燃えている、切り倒したのいずれかに関わらず、2つの座標が等しくなることはありません。

出力

単一の整数で、$T$分後に燃えている木の本数を出力してください。

採点

あなたのソリューションは、一連のテストケースグループでテストされます。 グループのポイントを得るためには、グループ内のすべてのテストケースに成功する必要があります。

グループ

ポイント

制限

$1$

$5$

$N = 1$, $M = 0$

$2$

$9$

$T \leq 100$, $M = 0$, $x_ i, y_ i < 100$

$3$

$10$

$T \leq 400$, $x_ i, y_ i < 100$

$4$

$11$

$M = 0$, $x_ i, y_ i < 100$

$5$

$21$

$x_ i, y_ i < 100$

$6$

$15$

$M = 0$

$7$

$29$

No further constraints

サンプルの説明

サンプル$1$では、火は$(0,2)$$(1,3)$$(2,2)$に燃え広がります。合計で、$4$本の木が燃えています。

サンプル$2$では、唯一の燃えている木は切り倒した木に囲まれています。 したがって、$T$がいくつであっても燃えている木は$1$本です。

サンプル$3$では、$T = 0$なので火が燃え広がる時間はなく、答えは$4$となります。

サンプル入力 1 サンプル出力 1
1 1 1
1 2
1 1
4
サンプル入力 2 サンプル出力 2
1 4 12345678
2 2
1 2
2 1
2 3
3 2
1
サンプル入力 3 サンプル出力 3
4 1 0
1 1
1 2
2 3
3 4
7 7
4
サンプル入力 4 サンプル出力 4
1 2 100000
0 0
2 1
1 2
20000199999