很久以前，小 M 和他的朋友小 N 一起筹备了一场编程比赛。他们一共拟出了 道题目，编号为 ，其中第 () 道题目的质量为非负整数 。
时光飞逝。如今，小 M 不再是信息学奥林匹克竞赛的选手，但他们曾约定要一起举办一系列的比赛。
小 M 并没有忘记这件事。
现在，小 M 希望将这 道题分成若干次训练赛，即将这 道题划分为若干个连续区间。题目的划分方案可以用一列整数表示：，表示将会有 次训练赛，第 次训练赛将包含所有编号在 到 （两端都包含）的题目。
此外，小 M 希望给参赛选手提供尽可能好的比赛。小 M 观察到，一场比赛的质量是由其最好的题和最后一个题共同决定的。所以他规定：一场训练赛的质量为其所包含题目 的最大值和所包含编号最大的题目的 的乘积。
小 M 还没有决定比赛的场数，目前只有 个候选值 。小 M 想知道，对于每个 ，在所有的划分题目至恰好 场训练赛的方式中，所有训练赛的质量总和最大是多少。
