Chàng lười Bờm quyết tâm luyện tập thể thao để gia tăng thể lực. Mỗi lần tập chàng ta dành ra \(N\) phút luyện tập, hình thức tập được chọn là chạy bộ.

Tham số quyết định quá trình tập của Bờm là "độ mệt mỏi", nó bằng \(0\) vào lúc bắt đầu tập và cần phải được đưa về \(0\) vào cuối buổi tập, độ mệt mỏi luôn không âm. Bờm có thể lựa chọn chạy hay nghỉ trong mỗi phút của thời gian tập.

• Nếu Bờm lựa chọn chạy trong phút thứ \(i\), anh chàng sẽ chạy được \(L_i\) mét đồng thời độ mệt mỏi sẽ gia tăng \(1\), tuy nhiên Bờm không thể tiếp tục chạy khi độ mệt mỏi đã đạt đến \(M\)
• Nếu \(X\) lựa chọn nghỉ, mỗi phút nghỉ sẽ làm độ mệt mỏi giảm \(1\) nếu nó lớn hơn \(0\), và một khi đã nghỉ, chàng ta sẽ nghỉ cho đến khi độ mệt mỏi giảm về \(0\), lúc đó Bờm có thể chạy tiếp (độ mệt mỏi gia tăng) hoặc nghỉ tiếp (độ mệt mỏi vẫn bằng \(0\)).

Bờm nhờ bạn xác định tổng độ dài quãng đường chạy lớn nhất anh ta có thể chạy được với các giới hạn kể trên.

Input

• Dòng \(1\): hai số nguyên \(N,M\) \((1 \leq N \leq 10000;1 \leq M \leq 500)\)
• Dòng \(2\ldots N+1\): \(N\) số nguyên là \(L_1,L_2,\ldots,L_N\) \((1 \leq L_i \leq 1000 \ \forall i=1÷N)\).

Output

• Dòng \(1\): số nguyên là tổng độ dài quãng đường Bờm chạy được lớn nhất.

Example

5 2
5 
3 
4 
2 
10

9