AT_KeioPC2025_n Times Table Sum

有一个 $N \times N$ 的网格。第 $i$ 行第 $j$ 列的格子用 $(i, j)$（$1 \le i, j \le N$）表示。 每个格子上写有一个整数，在 $(i, j)$ 格子上的数字为 $i \times j$。 我们称从 $(1,1)$ 开始，通过不断向右或向下移动到 $(N,N)$ 的路径为**好路径**。此时，好路径的分数定义为这条路径经过的所有格子上数字的总和。 记所有好路径分数的最大值为 $M$。请你求出不超过 $M$ 的整数中，作为任何好路径分数都不可能出现的最大的数是多少。

输入由标准输入按以下格式给出。 > $N$

请输出答案。

## 部分分 本题有部分分。 - 若你能正确解决 $N \le 30$ 的数据集，则可以获得 1 分。 ## 样例解释 1  比如，上图所示的路径： - 红色路径的分数为 $1 + 2 + 3 + 6 + 9 = 21$。 - 蓝色路径的分数为 $1 + 2 + 4 + 6 + 9 = 22$。 除此以外还可以考虑其他路径。对于 $N=3$ 的情况，$M=22$。而不超过 $M$ 的整数中，作为任何路径分数都不可能出现的最大数是 $20$。 # 数据范围 - $2 \le N \le 1000$ - 输入均为整数。 由 ChatGPT 5 翻译