题目描述

有$n$个未知数，每个数都是$0$或$1$，这些未知数已经按$1$到$n$编好了序。询问第$i$个未知数到第$j$个未知数的和的奇偶性，需要付出一定费用。给出询问每个区间[$i,j$]的和的奇偶性的代价。你需要设计一个询问的方案，使得你能推断出这$n$个每个数的值，并使代价的总和最小。

输入

第一行一个整数$n$； 第$i+1$行($1≤i≤n$)有$n+1-i$个整数，表示每一种询问所需的花费。 其中第$i+1$行第$j+1-i$个数$c[i,j]$表示对区间[$i,j$]进行询问的费用。

输出

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

输入样例

3
1 2 3
2 2
1

输出样例

4

提示

【数据规模】 对于20%数据，2 < N ≤ 5 对于50%数据，2 < N ≤ 50 对于100%数据，2 < N≤2000，1≤i≤j≤n，0≤c[i,j]≤10^9。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。