Problem Background

Matjia needs to paint his old fence.

Problem Description

The fence is made of $n$ wooden planks, each with a width of 1 centimeter and varying heights. For convenience and speed, he bought a super paint roller with a width of $x$ centimeters. However, the super paint roller comes with a catch—Matjia must always ensure that the roller is tightly in contact with the planks in its entirety, otherwise, the paint will drip around and stain everything. Additionally, the roller must always be parallel to the ground to prevent leaks. This means that for Matjia to use the roller safely, he needs to select $x$ planks and paint from the bottom of the lowest plank to the top in one go. Then, he selects some other planks and paints them, and so on.

This leaves some parts of the planks unpainted. Matjia must manually paint these parts with a brush. This is obviously quite tedious, so he asks you to write a program that calculates the minimum area he needs to paint manually. Since there is more than one way to achieve this, he also wants to know the minimum number of times he needs to use the super paint roller.

Input Format

The input consists of two lines.

The first line contains two integers $n$ and $x$, representing the number of planks and the width of the super paint roller, respectively.
The second line contains $n$ positive integers $h_1, h_2, \dots, h_n$, indicating the height of each plank.

Output Format

The output consists of two lines.

The first line contains an integer representing the minimum area Matjia needs to paint manually.
The second line contains an integer representing the minimum number of times Matjia needs to use the super paint roller, given that the manual painting area is minimized.

Sample Input and Output

Sample Input #1

5 3
5 3 4 4 5

Sample Output #1

3
2

Sample Input #2

10 3
3 3 3 3 3 3 3 3 3 3

Sample Output #2

0
4

Sample Input #3

7 4
1 2 3 4 3 2 1

Sample Output #3

4
4

Notes

[Sample 1 Explanation]

For Sample 1, Matjia needs to use the super paint roller twice.

• The first time, he paints planks 1, 2, and 3 with the super paint roller, painting to a height of 3 cm, resulting in a painted area of 9 cm².
• The second time, he paints planks 3, 4, and 5 with the super paint roller, painting to a height of 4 cm, resulting in a painted area of 12 cm².

Since there is a 3 cm² overlap in the two paintings, the remaining area that needs to be painted manually is $5 + 3 + 4 + 4 + 5 - 9 - 12 + 3 = 3$ cm². It can be proven that this scheme requires the minimum manual painting area and the minimum number of uses of the super paint roller.

[Data Range]

For all data, $1 \leqslant n \leqslant 10^6$, $1 \leqslant x \leqslant 10^5$, $1 \leqslant h_i < 10^6$.

[Problem Source]

This problem is from COCI 2009-2010 CONTEST 4 T4 FENCE, configured according to the original problem data, with a full score of 100 points.

Provided by Eason_AC for translation and arrangement.

见题面 Input 部分

见题面 Output 部分