Nộp hồ sơ đại học Có \(𝑀\) thí sinh đang nộp hồ sơ vào đại học \(X\). Có \(𝑁\) bàn làm việc để nhận hồ sơ của các thí sinh. Bàn thứ \(𝑘\) cần mất \(T[𝑘]\) giây để xử lí xong hồ sơ của một thí sinh. Tại thời điểm \(0\), tất cả các bàn làm việc đều trống. \(𝑀\) thí sinh xếp hàng, và một thí sinh có thể đến ngay một bàn làm việc còn trống để nộp hồ sơ. Bàn làm việc đó sẽ mất \(T[𝑘]\) giây để xử lí hồ sơ của thí sinh đó, và lại trống sau \(T[𝑘]\) giây để sẵn sàng nhận hồ sơ tiếp theo.

Yêu cầu: Tính sau ít nhất bao nhiêu giây tất cả các thí sinh có thể nộp xong hồ sơ.

Input

• Dòng đầu tiên chứa hai số nguyên \(𝑁\) và \(𝑀\).

• \(𝑁\) dòng tiếp theo, dòng thứ \(𝑘\) chứa số nguyên \(T[𝑘]\).

Output

In ra một số nguyên duy nhất là thời gian ngắn nhất để xử lí tất cả các hồ sơ.

Giới hạn: \(1≤𝑁≤10^5; 1≤𝑀≤10^9; 1≤𝑇[𝑘]≤10^9\).

Sample Input

2 6
7
10

Sample Output

28

Sample Input

7 10 
3 
8 
3 
6 
9 
2
4

Sample Output

8