Rio has become the president of Twinland. Now he wants to develop his country to fulfill his promise he made before the election. His country is a rectangle sized grid and there are some islands in his country. In each island, all the cities are connected and there exists some roads to go from any city to another city. But people from different islands can’t contact with each other. ণecause all the islands are separated from each other by water.
Rio is planning to build some flyovers between the islands such that they get connected and people from each island can visit the people of any other islands. He called some best engineers of his country to perform this job. After doing some research, the engineers have found out some interesting facts about the country.
Those islands where the number of cities are less than 100 are fully empty. No people lives there.
There’s a weight value for each of the cities and to build a flyover between two cities the construction cost is the difference of their weight values. For example, let's imagine u and v are two different cities whose weight values are p and q. So to build a flyover between them it will cost |p - q|.
If it is possible to reach v from u using a flyover then it will also be possible to reach other cities which exist in that island containing city v. Because after using the flyover, people can use the roads to visit other cities.
The engineers also made a proposal. They will only work on this project to build the flyovers if they are paid the salary of Wi dollars for each of the flyover they will have to build. For example, let's say they have to build the i'th flyover between the city c1 and c2 where c1 is one of the cities of island u and c2 is one of the cities of island v. If the total number of distinctly weighted cities of those two island u and v is p then Wi = p*p.
Rio is a very intelligent guy. To minimize the total cost, he wants to destroy all the islands where no people are living. So he only wants to build the flyovers among those islands where there exists at least 100 cities. Because building a flyover in an empty island will just be waste of money. He will pay all the construction cost at the beginning but will pay the salary of the engineers separately for each of the flyover they will have to build. The engineers will work on a single flyover at a time. He also doesn't want to pay much at a single time. So he wants to minimize the maximum salary of the engineers he will have to pay for building all the flyovers. Let’s say, engineers have built 5 flyovers. And they were paid 12, 28, 7, 18 and 20 dollars respectively. Here, the maximum salary that the engineers were paid at a time is 28. He wants to minimize this maximum salary. After minimizing this salary he also wants to minimize the total construction cost to build the flyovers, in such a way that all the islands get connected.
As you are the finance minister of the country, Rio wants you to make the most optimal plan that will satisfy all the conditions and then the engineers will start working as soon as you finish developing the plan.
Input
The first line contains two integer numbers N and M (1 ≤ N , M ≤ 500). N is the height and M is the width of the country. Then each of the next N lines contain M integers. If the value is 0 (zero) then the cell is part of water otherwise it’s a city and that value represents its weight . All the values are non-negative and less than 100. An island consists of some cities where from any city a person can go to all the other cities in the island. From any city, the possible movements are going left, right, top or bottom city.
Output
Output two integers in a single line. First integer is the value of the maximum salary Rio will have to pay at a time and the second integer represents the total construction cost to complete all the flyovers.
Samples
| Input | Output |
|---|---|
26 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 | 16 5 |
| Input | Output |
|---|---|
28 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 | 16 3 |
Note that at first Rio wants to minimize the maximum salary the engineers get at a time and then he wants to minimize the total construction cost.
