Two-Person Increasing Path Traversal

You are given a complete directed graph with N nodes numbered from 1 to N. Each edge from node i to node j (where i < j) has an associated weight. Two persons, both starting at node 1, must together visit every node in increasing order of their labels. In other words, if a person is at node i, they can only travel to a node j where j > i. At each step, you decide which person will move from his current node to the next unvisited node (which is always max(current positions)+1). The cost incurred is the weight of the edge used for that move. The goal is to determine the minimum total cost required for the two persons to collectively cover all nodes.

The problem can be formulated recursively. Let \(f(i, j)\) be the minimum additional cost needed when the first person is at node \(i\) and the second person is at node \(j\), with the next node to visit being \(k = \max(i, j) + 1\). The recurrence is given by:

[ f(i,j) = \min\big( A_{i,k} + f(k, j),; A_{j,k} + f(i, k) \big) \quad \text{for } k \leq N, ]

with the base case \(f(i,j)=0\) when \(\max(i,j) = N\). Both persons start at node 1.

inputFormat

The first line contains an integer N (the number of nodes).

Then for each i from 1 to N-1, there is a line with N-i space-separated integers. The j-th number in the i-th line denotes the weight \(A_{i,i+j}\) (the cost to go from node i to node i+j).

outputFormat

Output a single integer, which is the minimum total cost required for the two persons to traverse the nodes under the given rules.

sample

3
1 4
2

3