Swamp#241

Swamp

0.5 seconds
64 megabytes
Medium

The swamp has the form of a rectangle with sides parallel to the coordinate axes. Two opposite corners of the swamp have coordinates and (W, H), where and are positive integers. Inside the swamp, there are points (tussocks) with integer coordinates.

You are standing at the left edge of the swamp. You can cross the swamp by first jumping from the left bank to a point, then repeatedly jumping from point to point, and finally jumping from a point to the right bank.

However, for each jump, you require that the distance between each pair of consecutive points in your path is the same fixed value , and the distances from the left bank to the first point and from the last point to the right bank must not exceed .

Determine the minimal jump length that allows you to cross the swamp.

Input

The first line contains three integers: , , and . Each of the next lines contains two integers and — the coordinates of a point. 0 < W, H \leq 100; 0 < N \leq 1000.

Output

Output a single integer L^2, where is the required jump length.

Examples

Example 1

Loading
Loading