Vào một ngày đẹp trời, _minhduc rủ shiba cùng chơi một trò chơi điện tử với cậu ấy. Trò chơi ấy diễn ra như sau:

Có tất cả \(n\) điểm, được sắp xếp lần lượt từ điểm \(1\) tới điểm \(n\). Ở điểm thứ \(i\) sẽ diễn ra một loại trò chơi mà nếu thắng thì người chiến thắng sẽ nhận được \(a_i\) điểm. Người chơi đi từ điểm \(1\) đến điểm \(n\) và tham gia chơi các trò chơi trên đoạn đường đó, tuy nhiên do không thể chơi liên tục nên có một giới hạn được gọi là "thanh năng lượng". Thanh năng lượng của người chơi ban đầu là \(m\) và có giới hạn tối đa là \(m\). Nếu như "thanh năng lượng" của người chơi về \(0\) thì người chơi sẽ không thể chơi trò chơi mà cần phải nghỉ ngơi. Nếu nghỉ ngơi thì cần nghỉ ngơi tới khi đầy thanh năng lượng mới có thể chơi tiếp. Mỗi lần chơi một trò chơi, thanh năng lượng của người chơi bị sụt giảm đi \(1\) đơn vị.

Do là một người chơi tài năng, _minhduc tự tin rằng có thể chiến thắng tất cả các trò chơi, tuy nhiên giới hạn duy nhất của cậu ấy chính là thanh năng lượng kia. Cậu ấy cần phải kết thúc tất cả trò chơi với một thanh năng lượng đầy. Cậu ấy không biết cách chơi như thế nào để có thể tối ưu được số điểm của mình. Bạn hãy giúp _minhduc nhé!

Yêu cầu: Tính số điểm lớn nhất mà _minhduc có thể nhận được.

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n,m\) (\(1 \le n \le 10^5, 1 \le m \le 200\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2,..., a_n\) (\(a_i \le 10^9\)).

Output

• Một dòng chứa một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 20\).
• Subtask \(2\) (\(80\%\) số điểm): không có ràng buộc gì thêm.

Example

6 2
6 1 5 4 3 2

15