Wedding

One year after winning the Sapientia ECN contest, exactly on the date of ECN 2018, Andrei is getting married! Andrei is usually late. Maybe this is acceptable for different meetings, perhaps even those with his bachelor's thesis coordinator, but surely it is absolutely unacceptable to be late at your own wedding!! However, Andrei woke up late today as well, after all night he was up analyzing the stock market.

The area between Andrei's house and the wedding place is represented by a matrix of size N × M. Andrei's house is at cell (1, 1), and the wedding takes place at cell (N, M). Each minute Andrei can move to any of the 8 neighbor cells; that differ from his current cell with +1 / 0 / –1 on the line or column number.

There are also K slot machines around that Andrei is addicted to. Each slot machine i, with 1 ≤ i ≤ K; is defined by three numbers: S_i.x, S_i.y, the line and column number of its position; and S_i.a the addictiveness of slot machine S_i. For each free cell in the matrix, the danger level is defined by the sum of the addictiveness of each slot machine, proportional to the distance to it. More precisely, for a free cell at position (X, Y), the danger is:

Andrei needs to get to his wedding in at most T minutes. Knowing his addiction, he wants to choose a path for which the maximum danger level is as low as possible, while reaching his bride Lidia on time.

Input Specification

The first line of the input contains four numbers: N, M, K, and T, the size of the matrix, the number of slot machines, and the time Andrei has in minutes. Each of the following T lines contains three numbers: S_i.x, S_i.y, and S_i.a, the coordinates and addictiveness of slot machine i.

Input Limits, Constraints, and Clarifications

• 1 ≤ N, M ≤ 1000;
• 1 ≤ K ≤ 50;
• 1 ≤ S_i.a ≤ 10;
• 1 ≤ S_i.x ≤ N;
• 1 ≤ S_i.y ≤ M;
• max(N, M) < T ≤ N × M.
• Andrei's path cannot contain a cell with a slot machine.
• There are no slot machines at (1, 1) or (N, M).
• There is always a solution: love will find a way!
• Congratulations and best wishes for Lidia and Andrei!

Output Specification

Output one number, the minimum value of the danger he has to assume to reach the wedding on time. Print this value with exactly three decimals.

Sample Input

1. 6 7 3 7
2. 1 3 5
3. 3 6 7
4. 5 1 2

download as text file

Output for Sample Input

1. 53.083

download as text file

Explanation

The matrix is shown on the figure above. Andrei is at St, the wedding is at Fn, and the danger of the three slot machines is written at their positions.

The danger of each cell is shown in the top matrix of the following figure:

The danger of cell (2, 3) is:

5 × 13 / (|2 – 1| + |3 – 3|) + 7 × 13 / (|2 – 3| + |3 – 6|) + 2 × 13 / (|2 – 5| + |3 – 1|) = 5 × 13 / 1 + 7 × 13 / 4 + 2 × 13 / 4 = 65 + 22.75 + 5.2 = 92.95

Andrei can reach the wedding in 7 minutes, on a path with 8 cells total, out of which the most dangerous are the cells with danger 53.08. All paths with a smaller maximum danger would be longer, and Andrei would be late.