给定一个长度为 n 的自然数序列 a ,选择一个长度为 k ,元素均在 [1,n] 中的正整数序列 b ,使得 ∑ki=1abi−∏ki=1bi 最大。
输入格式
第一行两个正整数 n,k ,表示序列 a 的长度和序列 b 的长度。
第二行 n 个自然数 a1,a2,⋯,an ,表示序列 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×6×7=1334 。
数据范围
对于所有数据: 1≤k≤n≤106,0≤ai≤109 。
- 子任务 1 ( 4 分) n,k≤15 。
- 子任务 2 ( 8 分) n≤100,k≤5 。
- 子任务 3 ( 6 分) k=2 。
- 子任务 4 ( 15 分) n≤100,ai≤106 。
- 子任务 5 ( 8 分) n≤100 。
- 子任务 6 ( 7 分) n≤1000,k≤10 。
- 子任务 7 ( 8 分) n≤1000 。
- 子任务 8 ( 9 分) n≤105,k≤10 。
- 子任务 9 ( 11 分) n≤105 。
- 子任务 10 ( 10 分) k≤10 。
- 子任务 11 ( 14 分) 无特殊限制。