题目描述

给出长度为 $n$ 的序列 $a$ 和整数 $k$。
你可以将序列 $a$ 分为 $k$ 段（每段连续），从左到右依次编号为 $1$ 到 $k$。
令 $f(i)$ 表示元素 $a_i$ 所在的段的编号。
要求计算并输出

输入格式

• 第一行：两个整数 $n,k$。
• 第二行：$n$ 个整数，表示序列 $a$。

输出格式

• 输出最大值。

5 2 
-1 -2 5 -4 8

15

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

-43

4 1 
3 -1 6 0

8

数据范围

• 对 $100\%$ 的数据，满足$ (\lvert a_i \rvert \le 10^9)，(1 \le k \le n \le 10^6)$。
• 对于 $50\%$ 的数据，满足 $(n \le 5)$。
• 对于$90\%$ 的数据，满足$(n \le 5000)$。
• 对于 $100\%$ 的数据，满足 $(n \le 10^6)$。