Nobody rides far

matching optimization binary search maps and navigation logistics

Again n couriers and n orders with costs, metres of route along the streets, and each courier takes exactly one order. But the smallest sum may send someone across the whole city, and the couriers ask for something else: first let the longest trip be as short as possible, and only then the sum as small as possible.

Find the smallest possible value T of the longest trip, and among the assignments in which all trips are no longer than T, the assignment with the smallest sum.

In two tests the costs are distances along the streets of Almaty to cafés from OpenStreetMap, as in the article.

Input

The first line holds n (1 ≤ n ≤ 100). Then come n lines of n integers from 0 to 10⁹: the cost of the pair “courier i, order j”.

Output

The first line holds T. The second, the smallest sum with trips no longer than T. The third, n numbers: the order number for couriers 1, 2, …, n. If there are several suitable assignments, print any.

Examples

Example 1

Input

2
0 6
6 10

Output

6
12
2 1

Example 2

Input

Output

6
14
2 1 3

Limits

Time · Python: 8000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 10 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Suppose the threshold T is known. How can you check whether everyone can be assigned using only pairs no longer than T? If it is possible at T, is it possible at a larger threshold?

2Hint 2

Once the smallest threshold is found, pairs longer than it are forbidden. How can a pair be forbidden to the Hungarian algorithm without changing it?

3The idea

First, a binary search on the threshold among the distinct costs of the table. Checking a threshold is a question about a perfect matching in the bipartite graph of pairs no longer than T; it is solved by the Hopcroft–Karp algorithm or the ordinary search for augmenting paths from the article on matchings. If there is an assignment at T, there is one at any larger threshold too, so the binary search is legitimate.

Then the Hungarian algorithm, where the cost of every pair longer than T is replaced with a very large number, greater than the sum of any assignment of allowed pairs. An assignment of allowed pairs only exists, and any assignment with a forbidden pair is dearer than it, so the Hungarian algorithm’s answer contains no forbidden pairs.

4Walkthrough

In the first example the smallest sum is 0 + 10 = 10, but then the second courier drives 10. If the first takes order 2 and the second order 1, both trips are 6: T = 6, sum 12. In the second example there are two assignments with longest trip 6, with sums 14 and 16, and the first is needed: orders 2, 1, 3. The smallest sum overall, 10, would need a trip of length 7.

The forbidden cost is conveniently taken as 10¹⁵: the sum of allowed ones is at most 100 · 10⁹.

4+Solution

5Complexity

The binary search makes at most log₂(n²) ≈ 14 checks. Hopcroft–Karp is O(E√V), where E ≤ n². The Hungarian algorithm is O(n³). All together with n = 100 it is a few million operations.

6Common mistakes

Only the smallest sum. The Hungarian algorithm by itself does not look at the longest trip: the first example.
Only the threshold. Finding T is not enough: among the assignments with trips no longer than T the sums differ: the second example.
A greedy choice under the threshold. “Each courier the nearest free order no longer than T” can get stuck where an assignment exists: a real matching is needed.
The forbidden cost is too small. If it is less than the sum an assignment can reach, the Hungarian algorithm will sometimes choose a forbidden pair.

Algorithms behind it

GRA Algorithm Hungarian algorithm Which job for whom at the least total cost: potentials, tight pairs and augmenting paths in O(n³). O(n³) 2 problems GRA Algorithm Bipartite matching The largest number of pairs in a bipartite graph: Kuhn, Hopcroft–Karp, the theorems of König and Hall. O(E √V) 2 problems