COCI 2009/2010, Contest #4

Task OGRADA

Matija needs to paint his old fence. The fence is made from N planks, each 1 cm in width and varying in height. To do this easy and fast, he bought himself a Super Paint Roller Deluxe. The paint roller is X cm wide. The Super Paint Roller Deluxe model comes with a catch, however. Matija must at all times touch the planks with full width of the roller, otherwise paint drops all around and stains everything. Also, the roller must always be parallel to the ground to prevent leakage. This means that in order for Matija to use the roller safely, he needs to select X planks, and paint them from bottom to the top of the lowest plank in one swoop. Then he selects some other X planks, paints them and so on.

This leaves parts of some planks unpainted. Matija will have to paint such parts with a toothbrush. This is obviously quite tedious so he asked you to help him paint as much as possible using the Super Paint Roller Deluxe. Since there is more than one way to do this he is also interested in the painting that requires the minimal number of swoops.

Input

The first line of input contains two integer N (1 ≤ N ≤ 1 000 000), the number of planks, and X (1 ≤ X ≤ 100 000), the width of the Super Paint Roller. The width of the Super Paint Roller will not exceed the width of the fence.

The second line of input contains N positive integers, smaller than 1 000 000, the heights of planks in the fence.

Output

The first line of output should contain the smallest possible area Matija will have to paint manually.

The second line of output should contain the smallest number of swoops needed.

Scoring

If only one of the output numbers is correct, you will receive 50% of the points for that test case. You must always follow the output format to the letter, even if you do not calculate both numbers. In such cases, you may output any integer in place of the number you did not calculate.

Sample Tests

5 3
5 3 4 4 5

3
2

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

0
4

7 4
1 2 3 4 3 2 1

4
4

Explanation for Sample 1

Matija needs two swoops with his roller - one to paint planks 1, 2 and 3 to the height of 3 cm, the other to paint planks 3, 4 and 5 to the height of 4 cm. Note that 3 cm² (2 cm² on plank 1 and 1 cm² on plank 5) are left unpainted. Also, 3 cm² on plank 3 are painted over twice, but that's OK.

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 1.00s
Memory Limit: 32M
Added: Jul 14, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)