Background

Special for beginners, ^_^

Description

给出长度为 $n$ 的序列 $a$ 和整数 $k$ 。

你可以将序列分成 $k$ 段，从左到右按顺序标号。

令 $f\left(i\right)$ 表示位置 $i$ 属于的段的编号。

求 $\sum\limits_{i=1}^n \left(a_i·f(i)\right)$ 的最大值。

Format

Input

每个测试点包含多组测试例。

每组测试例包含两行。

第一行两个整数， $n,k，1\leq k \leq n\leq10^7$ 。

第二行 $n$ 个整数，表示序列 $a，|a_i|\leq10^{9}$ 。

单个测试点n的总和不超过$10^7$。

Output

对于每组测试例，在一行中输出最大值。

Samples

5 2
-1 -2 5 -4 8
7 6
-3 0 -1 -2 -2 -4 -1
4 1
3 -1 6 0

15
-45
8

Limitation

1s, 1024KiB for each test case.