408307: GYM103091 G Digging for Gold

William is competing in a gold mining contest against some Berkeley students. He's looking for gold nuggets buried in a giant field. The field can be modeled as an $$$N$$$ by $$$N$$$ grid of squares, where each grid square has the possibility of having golden nuggets buried underneath.

Since the field can be quite large, William bought a metal detector to aid in his search for gold. The metal detector can be used to find gold buried underneath the ground. In one use of the metal detector, it can find the number of gold nuggets buried under a $$$K$$$ by $$$K$$$ subgrid of the field. This subgrid must be axis-aligned and match exactly with the squares in the grid that form the field.

Unfortunately, since the metal detector is quite cheap, William can only use it once. Can you find help him find the maximum number of gold nuggets he can find?

Each test case begins with the integers $$$N, M, K$$$ $$$(1 \leq N, K \leq 10^9, 1 \leq M \leq 10^5).$$$

The next $$$M$$$ lines consist of two integers $$$x,y$$$ ($$$1 \leq x,y \leq N)$$$ denoting the coordinates of the square where a gold nugget can be found. Note that it is not guaranteed that coordinates are distinct, that is, more than one gold nugget can be buried underneath a given square.

A single integer, representing the maximum number of gold nuggets that the metal detector can find in one use.

5 5 3
1 1
2 2
1 2
4 5
5 5

3

5 3 1
2 2
3 3
2 2

2