给定一个长度为 $ 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\leq 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 $ 分） 无特殊限制。