야바위꾼

비토치는 장터에서 야바위로 먹고산다. 탁자 위에는 $1$번부터 $n$번까지 번호가 붙은 컵이 한 줄로 놓여 있고, 그중 몇 개의 컵 아래에 고무공이 하나씩 숨겨져 있다. 공이 숨겨진 컵을 하나도 빠짐없이 정확히 맞히는 손님은 커다란 곰 인형을 받는다.

비토치는 돈을 받고 힌트를 준다. $c_{ij}$원을 내면 $i$번 컵부터 $j$번 컵까지 아래에 숨겨진 공의 개수가 짝수인지 홀수인지 알려 준다.

바이타자르는 함께 온 바이티나에게 곰 인형을 선물하고 싶다. 하지만 확신이 서지 않은 채로 찍을 생각은 없다. 그래서 지금까지 산 힌트만으로 공의 위치가 하나로 정해질 때까지 힌트를 계속 산다.

힌트의 가격을 모두 알고 있을 때, 최악의 경우 얼마를 쓰게 되는지 구하려 한다. 즉, 비토치가 어떻게 답하든 $k$원 이하만 쓰고 공의 위치를 모두 알아낼 수 있는 질문 전략이 존재하는, 가장 작은 $k$를 구하라.

첫째 줄에 컵의 개수 $n$ ($1 \le n \le 2000$)이 주어진다.

이어지는 $n$개의 줄에 힌트의 가격이 주어진다. 그중 $i$번째 줄에는 정수 $n+1-i$개가 있고, 그 줄의 $j+1-i$번째 수가 $i$번 컵부터 $j$번 컵까지를 묻는 질문의 가격 $c_{ij}$이다 ($1 \le i \le j \le n$, $1 \le c_{ij} \le 10^9$).

최적의 전략을 썼을 때 공의 위치를 모두 알아내는 데 드는 최대 비용을 정수 하나로 출력한다.