[PA2014]Kuglarz

题目描述

魔术师的桌子上有 $n$ 个杯子排成一行,编号为 $1,2,…,n$,其中某些杯子底下藏有一个小球,如果你准确地猜出是哪些杯子,你就可以获得奖品。 花费 $c_{ij}$ 元,魔术师就会告诉你杯子 $i,i+1,…,j$ 底下藏有球的总数的奇偶性。 采取最优的询问策略,你至少需要花费多少元,才能保证猜出哪些杯子底下藏着球?

输入输出格式

输入格式


第一行一个整数 $n$。 第 $i+1$ 行($1\le i\le n$)有 $n+1-i$ 个整数,表示每一种询问所需的花费。 其中 $c_{ij}$(对区间 $[i,j]$ 进行询问的费用,$1\le i\le j\le n$)为第 $i+1$ 行第 $j+1-i$ 个数。

输出格式


输出一个整数,表示最少花费。

输入输出样例

输入样例 #1

5
1 2 3 4 5
4 3 2 1
3 4 5
2 1
5

输出样例 #1

7

说明

对于 $100\%$ 的数据,$1\le n\le 2\times 10^3$,$1\le c_{ij}\le 10^9$。