Rover Navigation with Battery Constraints

You are given an (n \times n) grid representing a terrain where a rover is deployed. Certain cells in the grid contain obstacles that the rover cannot traverse. The rover starts at the cell ((x_1, y_1)) and must reach the target cell ((x_2, y_2)). The rover has a limited battery that allows it at most (b) moves. Each move to an adjacent cell (up, down, left, or right) costs one unit of battery. Your task is to determine the minimum number of steps required for the rover to reach the target without exceeding the battery limit. If it is not possible to reach the target, output (-1).

Note: The grid is zero-indexed, and the list of obstacles is provided as coordinates. The rover cannot move onto a cell with an obstacle.

inputFormat

The input is read from standard input (stdin).

The first line contains seven space-separated integers: (n), (m), (x_1), (y_1), (x_2), (y_2), and (b), where (n) is the size of the grid and (m) is the number of obstacles.

This is followed by (m) lines, each containing two space-separated integers representing the coordinates of an obstacle.

outputFormat

Output a single integer on standard output (stdout) which is the minimum number of steps required for the rover to reach the target without exceeding the battery limit, or (-1) if it is not possible.## sample

5 3 0 0 4 4 8
1 0
1 1
1 2

8