ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1498. Stroke at Full Speed

Time limit: 1.0 second
Memory limit: 64 MB
Probably, most of you have heard about the step-by-step strategy game Losers-V produced by the company Lavin Interactive. If you are a fan of this game, you simply must help a knight to get out of a difficult situation.
In the course of a battle, the knight noticed a horned demon on the horizon. Without doubt, the knight had to attack the demon. It would seem to be very easy, just gallop and strike! But the knight is a special unit: the force of his stroke depends on the length of the run-up, which has limits. Help the knight to solve this tactical problem.
The battlefield is a rectangle N × M. At the start of the move the knight stands on the cell with coordinates (x1y1), and the horned demon is at the cell (x2y2). In one move, the knight can go to a cell that has a common side with the cell on which he stands at the moment. The knight is allowed to make not more than L moves in total (the stroke is not regarded as a move). It is not allowed to leave the battlefield (this would be regarded as a desertion) and to step on the cell with the horned demon. After the run-up, the knight may strike the demon from a cell which has a common side with the demon's cell. The stroke force is K + 1, where K is the length of the straight segment which the knight went immediately before the stroke. It is allowed to strike only once. The knight begs you to determine the maximal damage he can inflict on the horned demon. We assume that the damage equals the stroke force.


The first line contains three integers: N, M, and L (1 ≤ N, M ≤ 100; 1 ≤ L ≤ 1000). The second line contains the knight's coordinates (x1y1). In the third line there are the horned demon's coordinates (x2y2), 1 ≤ x1x2 ≤ N; 1 ≤ y1y2 ≤ M. The knight and the horned demon are in different cells.


Output the maximal damage to the demon which the knight can cause.


3 4 4
1 1
3 4


The knight moves to the cell (2, 1), then to (2, 4), and strikes. The length of the run-up is 3 and the corresponding stroke force is 4.
Problem Author: Alex Samsonov
Problem Source: XIII-th USU Junior Contest, October 2006