Phụ hồ bao năm nay làm thợ chính, Mặc sóng gió bôn ba, ta vẫn luôn yêu đời. Bao năm lạc trôi giữa nơi, Chỉ có xi măng và cát sỏi...

Nếu các bạn chưa biết, thợ lặn VL đã có một quãng thời gian làm thợ thi công cho các công trình trọng điểm quốc gia. Trong dự án lần này, chủ đầu tư giao cho đội của anh trọng trách mông má cho công trình, cụ thể là sơn tường.

Một bản thiết kế bức tường được ship hỏa tốc đến đôi tay của anh VL. Trên bản thiết kế có ~n~ cột, mỗi cột là một mảng của tường có chiều rộng là ~1~ cm và chiều cao là khác nhau. Để công việc dễ thở hơn, anh VL đã order nóng một con lăn sơn hiệu Vương liệm, với chiều rộng của con lăn là ~x~ cm.

Khi sơn, anh VL phải để con lăn song song với mặt đất, và vừa với chiều rộng của các mảng tường, nếu không sơn sẽ bắn tùm lum và tạo thành vết bẩn. Điều này có nghĩa là anh VL phải chọn ra ~x~ mảng tường ~1~ cm liên tiếp, rồi sử dụng con lăn để sơn chúng từ dưới lên trên cùng của mảng tường thấp nhất trong một lần. Sau đó, anh ta sẽ chọn tiếp ~x~ mảng tường khác và tiếp tục lăn sơn, cho đến mảng tường cuối cùng. Vì chủ đầu tư giàu, nên anh có thể lăn sơn ở những mảng tường đã được lăn.

Như vậy, một số phần tường sẽ không được sơn, và để xử lý những phần tường này, anh ta phải dùng một cái cọ vẽ rộng ~1~ cm. Điều này chắc chắn sẽ rất mệt mỏi, nhưng so với việc bị trừ lương và bị người yêu bỏ, thì anh bắt buộc phải làm.

Các bạn hãy giúp anh VL tính phương án lăn sơn "lười" nhất có thể nhé.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, x\ (1\le x \le n \le 10^6)~ – tương ứng với số mảng tường 1 cm và độ rộng của con lăn.

• Dòng thứ hai chứa dãy số nguyên dương ~h_1, h_2, \dots, h_n\ (1\le h_i < 10^7)~ – tương ứng với chiều cao của từng mảng tường.

Output

Đáp án in ra phương án lăn sơn tối ưu, bao gồm:

• Dòng đầu tiên chứa một số nguyên là diện tích tối thiểu mà VL phải sơn bằng cọ vẽ 1 cm trong phương án đó.

• Dòng thứ hai chứa một số nguyên là số lần sử dụng con lăn tối thiểu trong phương án đó.

Scoring

• Nếu chỉ in ra được diện tích tối thiểu, bạn sẽ được ~30\%~ số điểm.

• Subtask 1: ~40\%~ số điểm có ~n\le 200~.

• Subtask 2: ~40\%~ số điểm có ~n\le 10^5~.

• Subtask 3: ~20\%~ số điểm còn lại không có ràng buộc gì thêm.

Sample Input 1

5 3
5 3 4 4 5

Sample Output 1

3
2

Sample Input 2

7 4
1 2 3 4 3 2 1

Sample Output 2

4
4

Notes

Minh họa test đầu tiên, với phần gạch chéo là phần được lăn sơn: