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