Treasure Hunt in a Grid

In this problem, you are given an $N \times N$ grid that contains treasures and obstacles. You start at a given position and are allowed to move at most $L$ steps. Each move can take you up, down, left, or right. When you land on a cell containing a treasure, you collect it (and it is then removed from the grid). However, you cannot move into cells that contain obstacles. Your task is to determine the maximum number of treasures that can be collected within the allowed number of moves.

inputFormat

The input is read from standard input (stdin) and consists of four lines:

Line 1: Four integers $N$, $M$, $K$, $L$, where $N$ is the grid size (the grid is $N \times N$), $M$ is the number of treasures, $K$ is the number of obstacles, and $L$ is the maximum number of moves allowed.

Line 2: Two integers representing the starting coordinates $(sx, sy)$.

Line 3: If $M > 0$, this line contains $2M$ integers representing the positions of treasures in the format: $t_{1x}\ t_{1y}\ t_{2x}\ t_{2y}\ \ldots$. If $M = 0$, this line will be empty.

Line 4: If $K > 0$, this line contains $2K$ integers representing the positions of obstacles in the same format. If $K = 0$, this line will be empty.

outputFormat

Output a single integer on standard output (stdout) representing the maximum number of treasures that can be collected.## sample

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

3