33OJ
登录 注册

#P17737. [ICPC 2019 Xuzhou R] Factory

[ICPC 2019 Xuzhou R] Factory

Problem Description

You own a special beverage factory producing NN kinds of beverages.

There are KK machines in your factory, and each machine can produce all NN kinds of beverages. All KK machines can work in parallel. One machine can only produce one kind of beverage at a time, but machines can switch from producing a kind of beverage to another immediately.

Each machine has different production abilities. Specifically, it takes r×tijr\times t_{ij} minutes for the jj-th machine to produce rr liters of the ii-th beverage. Beverages are produced continuously, so the value of rr can be any real number.

Today, you got an order requesting 1 liter of each of all NN kinds of beverages. You want to finish the production as soon as possible. Thus, please write a program to calculate the minimum possible time to finish the production.

Input Format

The first line contains two positive integers N,KN, K (N≤2×104,K≤50N\leq 2\times 10^4, K\leq 50) --- the number of beverages and machines.

The next NN lines contain KK integers each. The jj-th number of the ii-th line contains the number tijt_{ij} (1≤tij≤501\leq t_{ij}\leq 50).

Output Format

Output one real number in a line, representing the minimum time to produce 1 liter of each of all NN kinds of beverages.

Your answer will be considered correct if the relative error does not exceed 10−210^{-2}.

3 3
1 2 3
2 1 3
6 6 3
2.000000
5 2
1 7
3 9
4 10
5 11
6 12
12.687500