Có ~ m ~ người cần làm thủ tục check-in tại sân bay quốc tế Cam Ranh để đi du lịch. Tại sân bay có ~ n ~ bàn có thể phục vụ công việc check-in. Mỗi người chỉ cần làm thủ tục tại một bàn bất kỳ nếu bàn đó đang trống và mỗi bàn chỉ phục vụ cho một người tại một thời điểm. Do kỹ năng làm việc của nhân viên tại mỗi bàn khác nhau nên thời gian phục cho một người tại mỗi bàn là khác nhau. Bàn thứ ~ i ~ ~ ( i = 1…n) ~ phục vụ một người mất ~ t_i ~ đơn vị thời gian. Thời gian chờ giữa hai người kế tiếp nhau tại mỗi bàn xem như không đáng kể.

Yêu cầu: Bạn hãy tính thời gian ít nhất để sân bay làm xong thủ tục check-in cho ~ m ~ người.

Dữ liệu vào

• Dòng đầu ghi hai số nguyên ~ n ~ ~ (1 ≤ n ≤ 10^5) ~ và ~ m ~ ~ (1 ≤ m ≤10^9) ~ cách nhau một dấu cách.
• Dòng thứ ~ i ~ ~ ( i = 1…n) ~ trong ~ n ~ dòng tiếp theo, mỗi dòng ghi một số nguyên ~ t_i ~ ~ (1 ≤ t_i ≤ 10^9) ~.

Kết quả

Một số nguyên duy nhất là số đơn vị thời gian ít nhất để sân bay làm xong thủ tục check-in cho ~ m ~ người.

Ràng buộc

• Có 70% số điểm với ~ m ≤ 30000 ~
• Có 30% số điểm với ~ 30000 ≤ m ≤ 10^9 ~

Ví dụ:

Input 1

2 6
7
10 

Output 1

28 

Input 2

7 10
3
8
3
6
9
2
4 

Output 2

8