Shortest Path in a Grid with Obstacles

You are given a grid with dimensions \( n \times m \) and a list of obstacles. The grid is 0-indexed, and you start at cell (0,0). Your task is to find the shortest path from the start to a given destination cell. You can move up, down, left, or right in one step.

The input includes an extra parameter \( k \) which does not affect the computation. Note that if the destination is exactly at (0, 0), the answer is 0. Also, if the destination cell is blocked by an obstacle, then output \( -1 \). If no valid path exists, print \( -1 \).

The shortest path distance is equivalent to the Manhattan distance when there are no obstacles. In the presence of obstacles, you must take a detour if possible.

inputFormat

The first line contains three integers \( n \), \( m \), and \( k \) where \( n \) and \( m \) denote the number of rows and columns of the grid respectively, and \( k \) is an extra parameter (unused in the logic).

The second line contains a single integer \( O \) denoting the number of obstacles.

Each of the next \( O \) lines contains two space-separated integers, representing the coordinates (row and column) of an obstacle.

The last line contains two integers \( x \) and \( y \), representing the destination cell.

All coordinates are 0-indexed.

outputFormat

Output a single integer representing the minimum number of steps required to reach the destination from (0, 0). If the destination is unreachable or blocked, output \( -1 \).

## sample

5 5 0
0
4 4

8