Hello, Pie!#1105
Pizzeria Pizazz prides itself on delivering pizza to its customers as quickly as possible. Unfortunately, only one driver can be hired for deliveries. Before starting a delivery, the driver waits for a certain number of orders to arrive (from to ). The driver then chooses the fastest possible route to deliver all the orders, even if it is necessary to visit the same location multiple times, including the pizzeria itself. At the end of the delivery route, the driver must return to the starting location, i.e., to the pizzeria. You are required to write a program to find the minimal time of such a route.
The first line contains a single integer (1 \le n \le 20) — the number of orders.
The next n + 1 lines each contain n + 1 integers. These numbers describe the travel times between locations: the pizzeria (numbered ) and the locations with orders (numbered from to ).
The -th value in the -th line represents the time required to drive directly from location to location without stopping at any other locations along the way.
Note that, due to traffic congestion and traffic lights, the direct travel time from to may not be shorter than going through other locations; travel times are not necessarily symmetric, that is, the time to go from to may differ from the time to go from to .
Print one integer — the minimal total time required to deliver pizza to all customers and return to the pizzeria.
Example 1