Background

A terrorist organization has planted a time bomb in a city, with great destructive power. The chief of police wants to know, in the worst case, how many blocks will be threatened.

Problem Description

In a city there are $N \times M$ blocks, each described by coordinates, as shown below:

It is known that a terrorist organization has planted a time bomb in one of the blocks, with power $t$, meaning all blocks whose straight-line (Euclidean) distance to that block is less than or equal to $t$ will be threatened. There are $k$ possible bomb locations. The chief wants to know, in the worst case, how many blocks will be threatened.

Input Format

The first line contains four positive integers $n, m, k, t$.

The next $k$ lines each contain two positive integers $x_i, y_i$, describing each possible block where the bomb may be placed.

Output Format

Output a single positive integer: the number of blocks that will be threatened in the worst case.

4 5 3 2
1 2
3 4
4 5

11

Hint

Constraints

For $20\%$ of the testdata, $k = 1$.

For $50\%$ of the testdata, $1 \le n, m \le 1000$, $1 \le k \le 20$, $1 \le t \le 100$.

For $100\%$ of the testdata, $1 \le n, m \le 10^5$, $1 \le k \le 50$, $t \le 300$.

fixed by @$\color{#5EB95E}{\textsf{Cppsteve}}$

Translated by ChatGPT 5