题号：NC212434
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
魔术师的桌子上有n个杯子排成一行，编号为1,2,…,n，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。花费c_ij元，魔术师就会告诉你杯子i,i+1,…,j底下藏有球的总数的奇偶性。
采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？
输入描述:
第一行一个整数n(1<=n<=2000)。
第i+1行(1<=i<=n)有n+1-i个整数，表示每一种询问所需的花费。其中c_ij（对区间[i,j]进行询问的费用，1<=i<=j<=n,1<=c_ij<=10^9）为第i+1行第j+1-i个数。
输出描述:
输出一个整数，表示最少花费。
示例1
输入
复制
5
1 2 3 4 5
4 3 2 1
3 4 5
2 1
5