k 取方格数

题目描述

给出一个 $n \times n$ 的矩阵，每一格有一个非负整数 $A_{i, j}$。现在从 $(1, 1)$ 出发，可以往右或者往下走，最后到达 $(n,n)$，每达到一格，把该格子的数取出来，该格子的数就变成$0$。这样一共走 $k$ 次，现在要求 $k$ 次所达到的方格的数的和最大。

对于$k = 1\sim n$都输出答案。

输入格式

第一行一个数 $n(1\leq n\leq 50)$。

接下来 $n$ 行，每行 $n$ 个数，分别表示矩阵的每个格子的数$A_{i, j} (1\leq A_{i,j} \leq 1000)$。

输出格式

一个数表示答案。

样例输入

3
1 2 3
0 2 1
1 4 2

样例输出

11
15
16