Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DTOGRADA - Sơn tường

Matija muốn sơn lại hàng rào nhà mình. Hàng rào của anh ấy được ghép bởi N tấm ván liên tiếp, mỗi tấm rộng 1 cm và có chiều cao khác nhau. Để sơn nhanh chóng và dễ dàng hơn, anh ấy đã mua "Super Pain Roller Deluxe" (một cây lăn xịn). Cây lăn có chiều rộng x cm. Mỗi lần dùng, anh ấy phải để cây lăn chạm vào bức tường hoàn toàn, nếu không sẽ không sơn được gì cả. Mặt khác, lúc nào cũng phải để cho cây lăn song song với mặt đất. Nói cách khác, anh ấy sẽ chọn ra x tấm ván liên tiếp và sơn từ dưới lên đến độ cao của tấm ván thấp nhất trong x tấm ván đó.

Tuy nhiên, cây lăn không thể giúp Matija sơn hết được hàng rào. Phần diện tích còn lại không thể sơn bằng cây lăn, anh ấy sẽ sơn bằng cọ nhỏ. Hãy giúp anh ấy tính xem phần diện tích phải sơn bằng cọ nhỏ nhất có thể là bao nhiêu, và số lần dùng cây lăn ít nhất để đạt được điều đó.

Input

  • Dòng đầu ghi số nguyên N (1 ≤ N ≤ 106) là số tấm ván cần phải sơn và số nguyên X (1 ≤ X ≤ 105).
  • Dòng tiếp theo ghi N số nguyên dương (mỗi số không quá 106) mô tả chiều cao của từng tấm ván.

Output

  • Dòng thứ nhất ghi diện tích nhỏ nhất phải sơn bằng cọ.
  • Dòng thứ hai ghi số lần dùng cây lăn ít nhất để đạt được diện tích đó.

Example

Input:
5 3
5 3 4 4 5

Output:
3
2


Được gửi lên bởi:khanhptnk
Ngày:2010-02-15
Thời gian chạy:0.400s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU PERL6 PYPY RUST SED
Nguồn bài:COCI 2009-2010 contest 4

hide comments
2010-02-15 13:07:22 Nguyễn Xuân Khánh
Được :)
2010-02-15 11:39:12 Huy Luu
Phần đã sơn rồi có được sơn đè lên ko anh ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.