급식 식자재 최소 입고량

문제

어느 학교의 급식실은 N일 동안 운영된다. 매일 아침 식자재 C인분이 입고되는데, C는 N일 내내 같은 0 이상의 정수이다. 입고된 식자재는 유통기한이 L일이어서, j일 아침에 입고된 분량은 j일부터 j+L-1일까지 사용할 수 있고, j+L일 아침에 남아 있으면 그 시점에 전부 폐기된다. i일째에는 정확히 d_i인분을 조리해야 한다. 하루의 순서는 먼저 폐기, 그다음 그날의 입고, 마지막으로 조리이다. 조리에 쓸 재고는 입고일이 가장 오래된 분량부터 차례로 사용하며, 한 입고분이 모자라면 다음으로 오래된 입고분에서 이어서 쓴다. 어느 날이든 사용 가능한 재고가 d_i인분에 못 미치면 급식은 실패한다. 급식이 단 하루도 실패하지 않는 가장 작은 C를 구하고, 그 C로 운영했을 때의 폐기 총량을 정산하라. 폐기 총량은 N일 이내의 아침에 유통기한이 지나 버려진 인분의 합이며, N일째 조리를 마친 뒤 남은 재고는 폐기로 세지 않는다. 주어진 입력에서는 C = max(d_i) 이면 항상 실패하지 않는다.

입력

첫 줄에 N 과 L 이 공백으로 구분되어 주어진다. 둘째 줄에 d_1, d_2, ..., d_N 이 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, 1 ≤ L ≤ N, 0 ≤ d_i ≤ 1,000,000,000 이며 모든 값은 정수이다.

출력

가장 작은 C 와 그 C 에서의 폐기 총량을 공백으로 구분해 한 줄에 출력한다.

5 2
3 0 0 4 1

3 3

3 1
2 5 1

5 3

출처: Devin.KR 자체 제작