Mr. Chudakov's Buses
Mr. Chudakov, after successfully completing a daring project, decided to invest his capital in the passenger transportation business. He has selected a set of cities between which he plans to establish transportation routes. He insists that the stops on these routes must always be in lexicographical order, from the city with the smallest name to the one with the largest. Lexicographical order means comparing words by their first letters, and if they are the same, comparing the second letters, and so on. However, his friends have pointed out that this might not always be practical (for instance, a route like Vinnytsia–Kyiv–Odesa–Sevastopol–Kharkiv–Yalta).
As a compromise, Mr. Chudakov is considering creating two bus routes. These routes should share the same starting city (the lexicographically smallest) and the same ending city (the lexicographically largest). Within each route, the cities should be ordered lexicographically, and every city must be included in at least one of the two routes. For example, with the cities mentioned above, one possible pair of routes could be Vinnytsia–Kyiv–Kharkiv–Yalta and Vinnytsia–Odesa–Sevastopol–Yalta.
Your task is to write a program to assist Mr. Chudakov in making this decision. The program should read the distance table between cities and determine two things: the length of the route that visits all cities in lexicographical order, and the minimum possible total length of the two routes that meet the compromise criteria (both starting at the lexicographically first city, ending at the lexicographically last, with all cities ordered within each route, and each city included in at least one route).
Input
The program will first read an integer N (3 ≤ N ≤ 2013), followed by N–1 rows. The first row contains N–1 numbers, representing the distances from the first city to the second, third, ..., N-th city. The second row contains N–2 numbers, representing the distances from the second city to the third, ..., N-th city, and so on, until the (N–1)-th row, which contains a single number representing the distance from the (N–1)-th city to the N-th city. All distances are strictly positive integers not exceeding 10^6. The distances satisfy the triangle inequality d(i,j)+d(j,k) ≥ d(i,k). The cities are already listed in ascending lexicographical order.
Output
The program should output two numbers separated by a space: the length of the route that visits all cities in lexicographical order, and the minimum possible total length of the compromise pair of routes.