Magic Cup and Ball

A magician has arranged n cups in a line, numbered from \(1\) to \(n\). Under some of these cups there is a hidden ball. Your task is to determine exactly which cups hide a ball. In order to do so, you are allowed to ask queries of the following form: by paying \(c_{ij}\) coins, the magician will tell you the parity (odd or even) of the total number of balls hidden under cups \(i, i+1, \ldots, j\) (i.e. the sum modulo \(2\)).

Using an optimal querying strategy, what is the minimum total cost (in coins) you must guarantee to pay in order to always be able to deduce the configuration of balls under the cups?

Hint: Interpret the ball placements as an \(n\)-dimensional binary vector. A query on cups \(i\) through \(j\) returns the inner product (modulo \(2\)) of this vector with the indicator vector of the interval \([i, j]\). It turns out that if you define \(f(k)=a_1+\cdots+a_k\) (modulo \(2\)) with \(f(0)=0\), then a query on the interval \(i\) to \(j\) is equivalent to obtaining \(f(j)\oplus f(i-1)\). Hence, obtaining the values \(f(1), f(2), \ldots, f(n)\) is sufficient to determine the original configuration. This observation allows you to model the problem as finding a minimum spanning tree in a complete graph with vertices \(0,1,\ldots,n\) where an edge between vertices \(u\) and \(v\) (with \(u<v\)) has weight \(c_{u+1,v}\) (the cost of querying cups \(u+1\) to \(v\)).

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 500\)), the number of cups. The following \(n\) lines describe the cost matrix. The \(i\)-th of these lines contains \(n-i+1\) integers: \(c_{i,i}, c_{i,i+1}, \ldots, c_{i,n}\) (each cost is an integer between 1 and 10⁹), representing the cost (in coins) to query the parity of cups \(i\) through \(j\) for \(j=i, i+1, \ldots, n\).

outputFormat

Output a single integer, the minimum total cost (in coins) required to guarantee that you can determine which cups have a ball hidden underneath.

sample

3
1 2 3
4 5
6

6