You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

有一个整数序列，请你将该序列分隔为长度最多为k的一些（连续）子串。分隔完成后，每个子串的中的所有值都会变为该子串中的最大值。 求该序列分割后数据值变换后所有元素的最大和。 返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。

输入

共两行，第一行是一个整数N(1≤N≤400) ，表示一共有N个整数以及一个整数k(1≤k≤350) ,表示分割的最多长度。 第二行是N个被空格分开的正整数ai，表示该序列的每一个整数((1≤ai≤10000) 。

Output

一个整数，为最大和.

样例

7 3
1 15 7 9 2 5 10

84

样例说明

按1-3，4，7-7分割，然后序列变成：15 15 15 9 10 10 10，这是元素和最大为84