Guards

Interview

Time limit2sMemory limit1024 MB

Summary

Count the guards in an n by m grid whose Manhattan distance to the ship at (x, y) is at most k, excluding the ship's own cell.

Level: Easy2 of 10
Topics: Brute force, Implementation
Solved: No attempts yet

Problem

Morpheus was captured by agents in the Matrix, and only he holds a license to pilot anti-gravity ships. Trinity could not handle the controls, so she drove the Nebuchadnezzar into a dead end. Every cell of the dead end holds a guard except the cell where the ship is. Unfortunately, the guards have blocked the way out of the compartment.

The compartment is small, only $n \times m$ cells, so destroying all the attacking guards will be easy. Moreover, the guards were built by Matrixsoft, so they cannot see the ship if it is more than $k$ cells away in Manhattan distance. In other words, a guard cannot see the ship when the sum of the absolute differences of their coordinates is greater than $k$ .

To fight them successfully, Trinity's team needs to know how many guards will attack. Find the number of guards that will attack the Nebuchadnezzar. In return, Trinity promises to finally pass her driving test.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n, m \le 1000$ ), the size of the compartment. The second line contains two integers $x$ and $y$ ( $1 \le x \le n$ , $1 \le y \le m$ ), the coordinates of the ship. The third line contains one integer $k$ ( $1 \le k \le 2000$ ), the distance within which the guards can see the ship.

Output

Print one integer: the number of guards that will attack the Nebuchadnezzar.

Examples1

Example 1
Input
```
2 2
1 1
1
```
Expected output
```
2
```