beecrowd | 2804


By Francisco Elio Parente Arcos Filho, UEA BR Brazil

Timelimit: 1

The North is the largest region of the country in area. With so much territorial extension and its 450 counties it was expected that there would be more Railroads, but this is not the reality. Much of the transportation is still done by highways or waterways.

To address this problem, Farcos has designed a rail network capable of connecting N counties of the North that he believes are strategic to commerce and tourism in the region. In this mesh a railroad always connects two different counties and has two rail lines that make the railroad capable of being traversed in both directions. In addition to always be possible to reach in all other N-1 counties from any countie in the network, either by a direct railroad or passing through other intermediate counties.

At the end of the design of its railway network and knowing the extension in km of each railroad, Farcos calculated which would be the smallest route between all the pairs of counties through the mesh and generated an array of distances which was attached to its design and sent to estimating the cost of producing such a project.

As the network design and matrix were not digitally shipped, the network design was lost and only the distance matrix arrived at the responsible authorities.

Its task is to use only the distance matrix and the average price informed to build one railway (regardless of its size), to estimate the lowest cost for the project.

However, care is needed. There are several people who are interested that the Farcos project does not even get to the analysis and may have altered positions of the distance matrix so that it does not correspond to a possible network designed by Farcos.


The first line of the entry contains two integers N (1 ≤ N ≤ 450) and K (1 ≤ K ≤ 102), respectively representing the number of strategic cities and the average price, in tens of thousands of reais, of building a railroad . The next N lines contain N integers Di,j (0 ≤ Di,j ≤ 106) each representing the distance in km from city i to city j through the rail network. Di,j ≠ 0 para i ≠ j.


The output consists of a single integer value representing the estimate of the minimum cost, in tens of thousands of reais, of constructing the railroad grid project. Or the message "*" if the distance matrix has changed.

Obs: It is guaranteed that the railroads have an integer size in km.

Input Samples Output Samples

3 1

0 10 20

10 0 10

20 10 0


5 8

0 3 4 9 5

3 0 5 6 2

4 5 0 11 7

9 6 11 0 4

5 2 7 4 0


3 7

0 2 3

4 0 6

7 8 0