0094. Railroad

Input file name:	railroad.in
Output file name:	railroad.out
Time limit:	20 s
Memory limit:	64 megabytes

The National Railroad of Dogsland consists of n stations. It is always guaranteed that there exists a route between any two stations. All citizens of Dogsland always select a cheapest route between two stations u and v, and the costs of these routes a_uv are known.

Once the Minister of Communication Paths of the Dogsland has discovered that no one buys valid tickets at the railroad ticket offices if the cost exceeds ten doglars. The citizens prefer to pay ten doglars fine (unofficial, of course) to the ticket inspectors! Nobody knows where the money goes then. Some tell that inspectors buy beer for this money.

The Minister is not pleased. He issued an edict to appropriate the funds for installing turnstiles at some k ≤ n stations.

Of course the direction of railroad wants to maximize the profit they will have after installing turnstiles. They have collected data about quantity of passengers going from station u to station v each day using very difficult methods (because passengers do not buy tickets!). Of course quantity from u to v may differ from quantity from v to u because some passengers may, for example, prefer to return by bus.

But everyone in Dogsland know their countrymen well enough to guess which algorithm they will use after installing turnstiles. It will be:

• If the cost of ticket is less or equal to ten doglars, the passenger always buys a legal ticket.
• If the destination station has turnstiles installed, the passenger has no way but to buy a legal ticket because the official penalty is very huge and may result in three month imprisonment.
• If the source station u has turnstiles installed, and the destination one v does not have them, the passenger searches for the station with the minimal cost of ticket from u (let us denote it w, w ≠ u). If a_uw+10<a_uv, the passenger buys a ticket to station w. Then when the inspectors discover that the ticket is invalid, the passenger gives them ten doglars fine and the inspectors successfully drink beer. Otherwise (if a_uw+10 ≥ a_uv) the passenger buys a legal ticket.
• In the remaining case, the passenger does not buy any tickets and pays fine.

Your task is to select k stations from n where turnstiles should be installed to maximize the profit.

Input file

The first line of input file contains two integers n and k (1 ≤ k ≤ n ≤ 24). The next n lines contain n integers each – the costs a_uv. Each line corresponds to one source station. All costs are positive integers (except a_uu) which do not exceed 10⁶. Then n lines follow, each also containing n integers b_uv in the same order. These non-negative integers are quantity of passengers going from station u to station v each day. None of them will exceed 10⁶.

It is always guaranteed that a_uu and b_uu are always equal to zero in input file. Ticket offices never sell the tickets from the station to itself.

Output file

Output in the first line the maximal possible total price of tickets sold during one day. Second line must contain exactly k different numbers in ascending order – the identifiers of stations where turnstiles should be installed to get this value. If there are several optimal solutions, output any of them.

Examples:

railroad.in	railroad.out
3 2 0 5 20 5 0 25 20 25 0 0 200 100 250 0 250 20 100 0	13400 2 3

Source: Petrozavodsk Summer 2003. Opening Contest, Friday, August 22
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version