Minimizing Manual Brushing on a Painted Fence

A fence is made of n wooden boards each of width 1 cm, but the boards may have different heights. Matija wants to paint the fence using a super paint roller with a fixed width of x cm. However, the roller has a strict restriction: it must be placed so that it is in full contact with x consecutive boards and it must always remain parallel to the ground. When Matija uses the roller on a chosen segment of boards, he must paint the boards from their bottom (ground level) upward until the roller contacts the top of the shortest board among those x consecutive boards. In other words, if the board heights in the segment are \(h_{i}, h_{i+1}, \dots, h_{i+x-1}\) then the roller paints a vertical band of height

[ d = \min_{j=i}^{i+x-1} ; h_{j}. ]

This operation paints the lower part of each board in the segment (by \(d\) centimeters). Any board that is taller than the painted portion will have its upper part unpainted; Matija must then brush these remaining (manual) parts with a toothbrush. Since manual brushing is tedious, Matija wants to maximize the area painted by roller passes (thus minimizing the area that must be brushed manually). Note that a board may be painted by several roller passes (but only the maximum painted height is counted per board) and the final manual area is the sum over boards of \(h_i - H_i\), where \(H_i\) is the highest point reached by any roller pass on board \(i\).

More formally, let the heights be \(h_1,h_2,\dots,h_n\). For any valid roller pass (which is an interval of exactly x consecutive boards) starting at index \(k\) (1-indexed), the operation increases the painted height on each board in the interval to at least

[ \min{h_k, h_{k+1}, \dots, h_{k+x-1}}. ]

For each board \(i\) define its optimal roller‐painted height as

[ F(i) = \max_{k,:, i\in [k,k+x-1]} ; \Bigl( \min_{j=k}^{k+x-1} h_j \Bigr). ]

Then the minimum manual area (i.e. the area to be brushed by hand) is

[ \text{Manual Area} = \sum_{i=1}^{n} \Bigl(h_i - F(i)\Bigr). ]

Since there can be more than one way to achieve the maximum roller‐painted area, Matija also wants to know the minimum number of roller passes required so that, for every board \(i\), one of the passes provides a roller painted height equal to \(F(i)\).

You are to write a program that, given n, x and the heights \(h_1, h_2, \dots, h_n\), computes two numbers:

• The minimum manual area (in square centimeters) that must be painted by hand.
• The minimum number of roller passes required to achieve that optimal outcome.

inputFormat

The first line contains two space-separated integers n and x (where 1 ≤ x ≤ n ≤ 2e5), representing the number of boards and the width of the roller in centimeters.

The second line contains n space-separated integers \(h_1, h_2, \dots, h_n\) (1 ≤ \(h_i\) ≤ 1e9) – the heights of the boards in centimeters.

outputFormat

Output two space‐separated integers on a single line:

• The minimum manual area (in square centimeters) that must be brushed manually.
• The minimum number of roller passes required to achieve that.

You may assume that the answer can be achieved by an appropriate sequence of roller passes.

sample

3 2
3 1 2

3 2