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 (x1, y1),
and the horned demon is at the cell
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
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
In the third line there are the horned demon's coordinates
1 ≤ x1, x2 ≤ N;
1 ≤ y1, y2 ≤ M.
The knight and the horned demon are in different cells.
Output the maximal damage to the demon which the knight can
3 4 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