Maximum Minimum Damage on a Grid

You are tasked with designing an optimal defense layout on an n×m grid. The cat‐invasion begins at point S and their destination is T. You, as part of the Earth Defense Team, can place up to K turrets and as many obstacles as you like on grid cells (except S and T). A cell that contains either a turret or an obstacle is blocked so that the invading cat people cannot step on it.

Each turret, when placed, attacks its 8 neighboring cells (in 8 directions: north, south, east, west, northeast, northwest, southeast, southwest). If a cell is within the attack range of one or more turrets, the damage incurred when passing through that cell is equal to the number of turrets attacking it.

You are allowed to place obstacles arbitrarily. In other words, you can force the invading cats to take any simple (non‐self intersecting) path from S to T that you choose, by placing obstacles on all other cells. Once the layout is fixed, the cat people will choose the S–T path that minimizes the total damage (i.e. the sum of the damage values on the cells along the path). Your goal is to design the layout (choose a simple path from S to T and place up to K turrets on cells not in the path) so that the damage incurred on the chosen path is maximized.

More formally, let P be a simple path (using moves in 4 directions: up, down, left, right) from S to T. For each cell v that is not on path P, if we place a turret at v, it will add 1 damage to every cell in P that lies in one of its 8 neighboring cells. You are allowed to choose at most K distinct turret positions. Under an optimal turret placement you will naturally choose those positions which yield the highest contributions to P (that is, a turret placed in cell v contributes c(v) damage where c(v) is the number of neighbors of v that lie in P).

Your task is to find the maximum possible total damage the cats must suffer, assuming you can force the invading cats onto the worst‐case path (i.e. the one that maximizes the sum of the top K contributions over all cells not on that path). Note that if there are less than K available cells not on P then you sum the contributions of all available cells.

Example:

Consider a 3×3 grid with S = (1, 0) and T = (1, 2) and K = 2. One possible forced path is (1,0) → (1,1) → (1,2). Then, for instance, cell (0,0) is adjacent to (1,0) and (1,1) (contribution 2), cell (2,1) is adjacent to (1,0), (1,1) and (1,2) (contribution 3) and so on. Choosing the two turret locations with the highest contributions might yield a total damage of 7. (See details in the problem statement.)

inputFormat

The input consists of three lines:

• The first line contains three integers n, m, and K (1 ≤ n, m ≤ 5, 1 ≤ K ≤ n*m), representing the dimensions of the grid and the maximum number of turrets you can place.
• The second line contains two integers s_x and s_y (0 ≤ s_x < n, 0 ≤ s_y < m), the coordinates of the starting position S.
• The third line contains two integers t_x and t_y (0 ≤ t_x < n, 0 ≤ t_y < m), the coordinates of the target position T. It is guaranteed that S ≠ T.

You may assume that coordinates are 0-indexed. You are allowed to place obstacles and turrets on any cell except S and T.

outputFormat

Output a single integer — the maximum total damage that can be forced on the invading cat people. In other words, over all choices of a simple S–T path (using only the 4 cardinal directions) and over all choices of at most K turret placements (on cells not in the chosen path), output the maximum achievable sum of damage on the forced path.

sample

3 3 2
1 0
1 2

7