Charmer--viv

题目背景

viv is a charmer....QwQ

题目描述

Loi54 的viv有另一个身份----魔♂术♂师,今天他要变一个魔♂术,但是,viv找不到他的魔法球了。一定是调皮的dc把球藏了起来。viv找到了dc,没想到腹黑的dc不光不交出viv魔法球,还向viv索要赎金。 作为一个安静的美男子,viv不想用暴♂力解决此事,再者dc还是viv的同学,所以viv忍气吞声,准备花RMB赎回自己的魔法球。 dc的服务态度“良♂好”,给出了详细的“询问”价格表。 价格表的形式如下: (dc把viv的魔法球放在一个区间内([1,n])的一个位置上) Cij: 代表询问[I,j]这个区间球的数量的奇偶性要付多少钱。 Viv没有多少钱,所以viv决定采取最优策略,花最少的钱来找出自己的球。 但是Viv不光是穷X,还是个蒟蒻,怎么可能找出最优策略,机智的viv想到了机智的你们…. Viv:“求帮忙….QwQ”

输入输出格式

输入格式


第一行一个整数n。 第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

输出样例 #1

7

说明

30%: n <= 50 60%: n <= 500 100% n <= 1600 (由于无法传输大文件,所以只能这么小了,我是不是太良心了..)