B. Collecting Strawberries
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Madeline is stuck in a grid, where she can only move up, down, left and right by one cell. She is currently in the first cell of the last row of the grid and wants to collect a strawberry in the last cell of the first row. Initially, Madeline is extremely fast so it takes her zero seconds to travel to a new cell, however, part of her (often referred to as Badeline) wants to slow her down. For every pair of adjacent cells, Badeline can increase the time it takes Madeline to traverse between two cells by a positive real number, $$$x$$$, for a cost of $$$x \cdot c$$$. Note that $$$c$$$ can differ between different pairs of cells. Assuming Madeline will take the shortest path to the strawberry after Badeline adds in the delays, determine the maximum shortest path Badeline can create for Madeline such that Badeline's total cost is at most $$$k$$$.

Input

The first line of input will consist of three integers, $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \leq n, m \leq 1000$$$, $$$1 \leq k \leq 10^9$$$) — the number of rows and columns in the grid and the max total cost.

For the following $$$n$$$ lines, the $$$i$$$-th line will consist of $$$m-1$$$ integers, $$$c_{r,i,j}$$$ indicating the cost rate of increasing the time it takes to traverse between cells $$$(i, j)$$$ and $$$(i, j+1)$$$, where $$$(i, j)$$$ denotes the $$$j$$$-th cell of the $$$i$$$-th row.

For the following $$$n-1$$$ lines, the $$$i$$$-th line will consist of $$$m$$$ integers, $$$c_{c,i,j}$$$ indicating the cost rate of increasing the time it takes to traverse between cells $$$(i, j)$$$ and $$$(i+1, j)$$$, where $$$(i, j)$$$ denotes the $$$j$$$-th cell of the $$$i$$$-th row.

All cost rates are between $$$1$$$ and $$$10^9$$$.

Output

Output a single real number — the longest shortest path Badeline can create for Madeline. Your answer will be accepted if it has an absolute or relative error of $$$10^{-6}$$$ with the judge's solution.

Examples
Input
2 2 3
1
1
1 1
Output
1.5000000000
Input
3 3 4
3 6
2 5
1 4
1 3 5
2 4 6
Output
1.3333333333