Worst-case Bomb Threat Coverage

In a city, the blocks are arranged in an $N \times M$ grid. Each block is identified by its coordinate \((i, j)\), where \(1 \le i \le N\) and \(1 \le j \le M\). A terrorist organization has placed a timed bomb in one of these blocks. The bomb has a threat radius \(t\), meaning that all blocks whose direct (Euclidean) distance from the bomb's block satisfies
\[ \sqrt{(i-x)^2+(j-y)^2} \le t \]
are threatened, where \((x,y)\) is the bomb location.

There are \(k\) possible bomb placement locations provided. The task is to determine, in the worst-case scenario (i.e. if the bomb is placed in the position that threatens the most blocks), how many blocks will be affected.

inputFormat

The first line contains four space-separated integers \(N\), \(M\), \(t\), and \(k\). Each of the next \(k\) lines contains two space-separated integers \(r\) and \(c\), representing a potential bomb placement at block \((r, c)\).

outputFormat

Output a single integer representing the maximum number of blocks that could be threatened in the worst-case scenario.

sample

5 5 1 2
1 1
3 3

5