Phái đoàn Croatia gồm ~M~ người sẽ tới dự IOI 2013 tại Úc. Hiện tại họ đang xếp hàng chờ làm thủ tục tại sân bay. Có ~N~ bàn làm thủ tục đang mở. Một số quan chức làm việc hiệu quả hơn những người khác nên các bàn làm việc có tốc độ khác nhau. Tại bàn thứ ~k~, cần có ~T_k~ giây để hoàn tất việc làm thủ tục cho một hành khách và các thành viên trong đoàn của chúng tôi tình cờ biết được con số chính xác.

Lúc đầu, tất cả các bàn đều sẵn sàng đón hành khách tiếp theo và các thành viên trong đoàn là những người duy nhất xếp hàng. Một người chỉ có thể chiếm (bắt đầu đăng ký tại) một bàn trống khi tất cả những người ở phía trước người đó trong hàng đợi đã rời khỏi hàng đợi (đã bắt đầu, không nhất thiết phải kết thúc, đã đăng ký). Tại thời điểm đó, người đó có thể ngay lập tức chiếm một bàn làm việc có sẵn (nếu có), nhưng cũng có thể chọn đợi một bàn làm việc khác (nhanh hơn) có sẵn. Các thành viên trong đoàn của chúng tôi, là những người đam mê khoa học máy tính, đưa ra quyết định này sao cho thời điểm tất cả họ hoàn tất việc đăng ký là càng sớm càng tốt. Nhiệm vụ của bạn là tìm ra thời điểm đó.

Hãy để chúng tôi mô tả kịch bản từ ví dụ đầu tiên dưới đây. Có hai bàn, thời gian xử lý lần lượt là 7 và 10 giây. Trong số sáu người trong đoàn, hai người đầu tiên ngồi ngay vào hai bàn. Đến lúc 7, bàn đầu tiên được giải phóng, người thứ ba chiếm giữ. Lúc 10 giờ, người thứ tư ngồi ở bàn thứ hai. Lúc 14, người thứ năm ngồi ở bàn thứ nhất. Đến thời điểm 20, bàn thứ hai lại được giải phóng, nhưng người thứ sáu quyết định đợi thêm một giây nữa (thời gian 21) để bàn thứ nhất có sẵn rồi chiếm giữ. Bằng cách này, quá trình đăng ký sẽ hoàn tất trước thời gian 28. Nếu người thứ sáu không đợi bàn nhanh hơn thì quá trình đăng ký sẽ mất tổng cộng 30 giây.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ ~(1 \le N \le 100 000)~ là số bàn và ~M~ ~(1 \le M \le 1 000 000 000)~ là số người trong đoàn.
• Mỗi dòng trong số ~N~ dòng tiếp theo chứa một số ~T_k~ từ câu lệnh bài toán ~(1 \le T_k \le 10^9)~.

Output

• Dòng đầu ra đầu tiên và duy nhất phải chứa thời gian tối thiểu được yêu cầu tính bằng giây.

Scoring

• Trong dữ liệu thử nghiệm có tổng điểm là ~75~, số ~M~ sẽ tối đa là ~300 000~.

Sample Input 1

2 6
7
10

Sample Output 1

28

Sample Input 2

7 10
3
8
3
6
9
2
4

Sample Output 2

8