题目描述

魔术师的桌子上有 $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$ 个数。

输出格式

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

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

7

提示

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