给定一个长度为 $n$ 的自然数序列 $a$ ，选择一个长度为 $k$ ，元素均在 $[1,n]$ 中的正整数序列 $b$ ，使得 $\sum_{i=1}^{k}a_{b_i}-\prod_{i=1}^{k}b_i$ 最大。

输入格式

第一行两个正整数 $n,k$ ，表示序列 $a$ 的长度和序列 $b$ 的长度。

第二行 $n$ 个自然数 $a_1,a_2,\cdots,a_n$ ，表示序列 $a$ 。

输出格式

仅一行一个自然数，表示答案。

样例输入 1

10 3
185 327 366 422 478 516 550 567 560 583

样例输出 1

1334

样例 1 解释

当 $b=[5,6,7]$ 时，取到最大值 $478+516+550-5\times 6\times 7=1334$ 。

数据范围

对于所有数据： $1\leq k, n\leq 10^6,0\leq a_i\leq 10^9$ 。

• 子任务 $1$ （ $4$ 分） $n,k\leq 15$ 。
• 子任务 $2$ （ $8$ 分） $n\leq 100,k\leq 5$ 。
• 子任务 $3$ （ $6$ 分） $k=2$ 。
• 子任务 $4$ （ $15$ 分） $n\leq 100,a_i\leq 10^6$ 。
• 子任务 $5$ （ $8$ 分） $n\leq 100$ 。
• 子任务 $6$ （ $7$ 分） $n\leq 1000,k\leq 10$ 。
• 子任务 $7$ （ $8$ 分） $n\leq 1000$ 。
• 子任务 $8$ （ $9$ 分） $n\leq 10^5,k\leq 10$ 。
• 子任务 $9$ （ $11$ 分） $n\leq 10^5$ 。
• 子任务 $10$ （ $10$ 分） $k\leq 10$ 。
• 子任务 $11$ （ $14$ 分） 无特殊限制。