样例下载

【问题描述】

你正在参加一个猜数游戏。

主持人把 N 个数排成一排，这些数不是 0 就是 1。

主持人让你猜一下每个数是什么。

你可以询问主持人任意一个区间内的数的和。

但是主持人并不会告诉你答案，只会告诉你这个区间内的数的和是奇数还是偶数。

询问区间 [i, j] 需要付出 $A_{ij}$ 的代价。

问：你全部猜对最少需要付出多少代价？

【输入格式】

第一行：一个整数 N

接下来有 N 行：

• 第 i 行有 N-i+1 个整数，询问区间 [i, j] 需要付出的代价 $A_{ij}$ 即是其中第 i 行第 j-i+1 个数。

【输出格式】

一个整数，表示最少代价。

【输入样例】

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

【输出样例】

7

【数据范围】

100% 的数据：$1 ≤ N ≤ 2000, 1 ≤ A_{ij} ≤ 10^9$