Given a sequence $a$ of $n$ natural numbers, choose a sequence $b$ of length $k$ where each element is in the range $[1, n]$, such that $\sum_{i=1}^{k}a_{b_i}-\prod_{i=1}^{k}b_i$ is maximized.
Input
The first line contains two positive integers $n$ and $k$, representing the length of sequence $a$ and the length of sequence $b$, respectively.
The second line contains $n$ natural numbers $a_1, a_2, \dots, a_n$, representing the sequence $a$.
Output
Output a single natural number representing the maximum value.
Examples
Input 1
10 3 185 327 366 422 478 516 550 567 560 583
Output 1
1334
Note 1
When $b=[5, 6, 7]$, the maximum value is $478+516+550-5\times 6\times 7=1334$.
Constraints
For all data: $1\leq k, n\leq 10^6, 0\leq a_i\leq 10^9$.
- Subtask 1 (4 points): $n, k\leq 15$.
- Subtask 2 (8 points): $n\leq 100, k\leq 5$.
- Subtask 3 (6 points): $k=2$.
- Subtask 4 (15 points): $n\leq 100, a_i\leq 10^6$.
- Subtask 5 (8 points): $n\leq 100$.
- Subtask 6 (7 points): $n\leq 1000, k\leq 10$.
- Subtask 7 (8 points): $n\leq 1000$.
- Subtask 8 (9 points): $n\leq 10^5, k\leq 10$.
- Subtask 9 (11 points): $n\leq 10^5$.
- Subtask 10 (10 points): $k\leq 10$.
- Subtask 11 (14 points): No special restrictions.