该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

公司的年终大会上，小B 为了收买人心 举行了一个猜球游戏。

题目描述

有 $n$ 个杯子编号为 $1,2,…,n$，从左到右排成一行，所有的杯子都倒着扣在桌上。其中某些杯子底下藏有一个小球，如果小A能准确地猜出哪些杯子中藏了小球，小A就能获得奖品。

黑心商家小B规定，花费 $c_{ij}$ 元就能知道第 $i$ 个杯子到第 $j$ 个杯子之间（包括两端）球的数量是奇数还是偶数。

小A希望猜出每个杯子底下是否藏着小球。但是小A带的钱不多，他希望采用最佳询问策略，请你告诉小A他最少需要花多少钱？

输入格式

第一行一个正整数 $n$。

第 $i+1$ 行（ $1 \le i \le n$ ）有 $n+1-i$ 个整数，表示 $c_{ij}$。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

7

提示

对于 $40\%$ 的数据，$1 \le n \le 5$。

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