T429208 「YAC Round 6」琪露诺的小球猜猜游戏


琪露诺和大酱在玩一个小球猜猜的游戏。 大酱有 $n$ 个纸杯，排成一行，编号为 $1, 2, \ldots, n$。其中，有一些杯子底下藏有小球。如果琪露诺可以准确无误地找出哪些纸杯下有小球，那么她就会得到大酱一个大大的拥抱。 琪露诺需要消耗 $c_{i,j}$ 智商知道纸杯 $i, i + 1, i + 2, \ldots, j$ 下藏有 **小球总数的奇偶性**。 虽然琪露诺的智商高达 $999999999$，但是她还是想要尽可能少地消耗自己的脑力。请问琪露诺 **最少需要消耗多少智商**，才能保证自己准确无误地猜出哪些纸杯底下有小球。

第一行输入一个整数 $n$。 接下来有 $n$ 行，其中第 $i$ 行有 $n-i+1$ 个整数。每一行为 $c_{i , i}, c_{i, i + 1}, \ldots, c_{i, n}$ 。 其中 $c_{i,j}$ 为知道区间 $[i,j]$ 的纸杯下藏有小球总数奇偶性的所消耗的智商。

输出一个整数，表示最少消耗。

$1\le n\le 2\times 10^3$，$1\le c_{ij}\le 10^9$。