wwx 的粉刷计划

题目描述

wwx 最近准备做个手工，她从仓库里找出来了 $n$ 块宽度均为 $1$ 的木板。

现在她打算给这些木板涂上一样颜色的油漆，看起来漂亮一些。

她把这 $n$ 块木板宽度为 $1$ 的边靠在墙边对齐，依次排成一排，第 $i$ 块木板的长度为 $a_i$

但是 wwx 的滚筒宽度却是 $k$，也就是意味着 wwx 只能一次性同时给 $k$ 块木板从下往上刷漆

如果滚筒在刷漆的过程中，触及到了木板以外的部分，就会把油漆滴落在家里的各处地方，然后被妈妈一顿胖揍

显然 wwx 不希望发生这样的惨剧，但是她又希望能尽可能的给木板涂上油漆，所以她想请你帮帮她

告诉她最多能给多大面积的木板涂上油漆，以及相应最小的刷漆次数

输入格式

输入第一行包含两个正整数 $n,k$，分别表示木板数量以及滚筒宽度

输入第二行包含 $n$ 个整数，第 $i$ 个数字表示第 $i$ 块木板的高度 $a_i$

输出格式

输出两行各一个整数，第一行表示最多能涂上油漆的面积 第二行表示最少的刷漆次数

数据范围

对于 $20\%$ 的数据保证：$n \leq 10, k \leq 10$

对于 $50\%$ 的数据保证：$n \leq 10^3, k \leq min(10, n)$

对于 $75\%$ 的数据保证：$n \leq 10^3, k \leq n$

对于 $100\%$ 的数据保证：$n \leq 2 * 10^5, k \leq n, 1 \leq a_i \leq 10^9$

样例输入

5 2
1 2 4 2 3

样例输出

9
3

样例解释

三次刷漆区间分别为：$[1,2], [2,3], [4,5]$