配点 : 101 点
問題文
N×N 我有一个正方形网格。从上面 i 行,从左起 j 选择列中的方块。 (i,j)(1≤i,j≤N) 。
每个方格都有一个整数 1 上面写道,(i,j) 有 写入 i×j 。 从
(1,1) 开始并重复移动到右侧或底部的方块, 前往 (N,N) 的路线好路线 它被称为。此时,好路线的分数被定义为“所经过的方格上写的数字的总和”。
一条好路线的最大可能得分是 M 。M 找到未显示为良好路线分数的最大整数。
制約
- 2 \le N \le 1000
- 所有输入均为整数 如果正确答案是满足
部分点
针对此问题设置了部分分数。 如果正确答案是满足
- N \le 30 的数据集 1 点。 如果正确答案是满足
入力
输入将以以下格式从标准输入给出。
N
出力
打印答案。 每个加油站的
入力例 1
3
出力例 1
20

例如,考虑上图中所示的路线。
- 红色路线的分数是 1 + 2 + 3 + 6 + 9 = 21 。
- 蓝色路线的得分是 1 + 2 + 4 + 6 + 9 = 22 。
还有其他可能的路线,但是N = 3 如果是 M = 22 。并且,M 不作为路线分数出现的最大整数是 20 。
入力例 2
6
出力例 2
152
入力例 3
9
出力例 3
476