A campus network is constituted by n computers, which are mutually connected by net line,as the picture shows.The vertexs represent computers, the edges represent net lines.As you see, different net lines have different transmission capacities, for example, it will take 32 sec to transmit information from Computer 1 to Computer 2, while 10 sec from 2 to3, and at least 44 sec from 1 to 5(through v3).Now we know that the school has bought m accelerating devices, each of which can halve the transmitting time of a net line. One net line can afford multiple devices, that is to say,when 2 devices are connected to one line, the time will be shorten to 1/4 of the original one, thus 1/8 when 3 devices are used. It remains an urgent problem that how to distribute those devices approprately to make the time shortest from 1 to n.The school officials employ you to solve this problem.As the it shows, if m=2, that is to say ,two devices are used for Line 1-3 and Line 3-5, then the time will be 22 sec.


Input as follows.The first row has integer n and m(1 < n <= 100,0 <= m <= 10). The following n rows, each row has n real numbers.Row i and Column j mean the Computer i and Computer j are connected.0 means no line between the computers. (fabs() is recommended)


Output the shortest time from 1 to n by m devices.Printed exact to two digits to the right of the decimal point.

Sample Input

5 2 0 34 24 0 0 34 0 10 12 0 24 10 0 16 20 0 12 16 0 30 0 0 20 30 0

Sample Output