홍준이와 울타리

홍준이는 오래된 울타리를 칠해야 한다. 이 울타리는 너비가 1cm인 널빤지 N개로 이루어져 있고, 널빤지의 높이는 서로 다를 수 있다. 더 빨리 칠하기 위해 홍준이는 폭이 Xcm인 Super Paint Roller Deluxe 롤러를 샀다.

칠하는 동안 롤러의 모든 부분은 널빤지를 벗어나면 안 된다. 벗어나면 페인트가 흘러 주변을 더럽힐 수 있다. 또한 롤러는 항상 땅과 평행해야 한다. 따라서 안전한 한 번의 롤러질은 연속한 X개의 널빤지를 고른 뒤, 그 X개 중 가장 낮은 널빤지의 전체 높이까지 바닥부터 한꺼번에 칠하는 것이다. 홍준이는 이런 작업을 다른 연속한 X개의 널빤지에 대해 반복할 수 있다.

이 방식으로 칠하면 롤러로 칠하지 못한 부분이 남을 수 있고, 그 부분은 칫솔로 칠해야 한다. 이 작업은 지루하므로, 홍준이는 롤러로 칠할 수 있는 면적을 최대화하려고 한다. 최대 면적을 칠하는 방법이 여러 가지라면, 그중 롤러질 횟수가 가장 적은 방법을 원한다.

칫솔로 칠해야 하는 널빤지 면적의 최솟값과, 그때 필요한 롤러질의 최소 횟수를 구하는 프로그램을 작성하시오.

첫째 줄에 널빤지의 수 N (1 <= N <= 1,000,000)과 롤러의 너비 X (1 <= X <= 100,000, X <= N)가 주어진다.

둘째 줄에 각 널빤지의 높이를 나타내는 1,000,000 이하의 자연수 N개가 주어진다.

첫째 줄에 홍준이가 칫솔로 칠해야 하는 널빤지 면적의 최솟값을 출력한다.

둘째 줄에 그 면적을 달성하기 위해 필요한 롤러질의 최소 횟수를 출력한다.