시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 275 123 96 44.240%

문제

TSP는 매우 유명한 문제이다. 이 문제는 NP-hard 문제이기 때문에 효율적인 해법이 존재하지 않는다. 이번에는 약간 변형된 TSP 문제를 풀어보자.

TSP문제는 도시 N개를 모두 한 번씩 방문하는 문제이다. 도시는 1번부터 N번까지 번호가 붙여져 있다. 각 도시 사이의 거리는 모두 알려져 있으며, 모든 도시를 방문하는데 드는 시간을 최소로 해야 한다.

번호가 K인 도시를 방문하려면, K보다 작은 번호를 가진 모든 도시를 K번을 방문하기 전에 모두 방문하거나, 방문한 후에 모두 방문해야 한다. 즉, K보다 번호가 작은 도시 중 하나를 K번 이전에 방문하고, 다른 하나를 K번 이후에 방문하면 안된다.

위의 조건을 만족하면서 모든 도시를 방문하는데 드는 시간의 최소값을 구하는 프로그램을 작성하시오. 첫 도시와 마지막 도시는 같지 않아도 되며, 어느 도시에서 시작하고 마쳐도 상관없다.

입력

첫째 줄에 도시의 수 N (2 ≤ N ≤ 1500)이 주어진다.

다음 N개 줄에는 [0, 1000] 구간에 포함되는 양의 정수가 주어진다. A번째 행의 B번째 숫자는 A에서 B로 가는데 필요한 시간이고, 이 수는 B번 행의 A번째 숫자와 같다. A와 B가 같은 경우에는 0이 주어지며, 이외의 경우에는 항상 양의 정수이다.

출력

첫째 줄에 문제의 조건을 만족하면서 모든 도시를 방문하는데 드는 시간의 최소값을 출력한다.

예제 입력

3
0 5 2
5 0 4
2 4 0

예제 출력

7

힌트

가능한 방문 순서는 2, 1, 3과 3, 1, 2가 있다. 1, 3, 2가 시간이 더 적게 들지만, 문제의 조건을 만족하지 않는다.