Tí rất yêu thích và học giỏi môn Tin học, vì vậy năm nay Tí đã đăng ký tham dự kỳ thi HSG lớp ~10~ do nhà trường tổ chức. Vào buổi thi, sau khi nhận được đề Tí thấy đề thi có ~n~ bài, bài thứ ~i~ có số điểm là ~d_i~. Sau khi phân tích kỹ các bài Tí thấy với khả năng của mình thì thời gian để làm mỗi bài là như nhau và mình chỉ đủ thời gian làm ~k~ bài. Tuy nhiên quy định của BTC lại không cho phép thí sinh bỏ qua hai bài liên tiếp (nếu thí sinh bỏ qua bài thứ ~i~ và bài thứ ~i + 1~ thì tất cả các bài từ bài thứ ~i~ trở đi đều không được tính điểm). Tất nhiên với trí thông minh của mình thì Tí có thể lựa chọn các bài để làm sao cho đạt được số điểm tối đa. Em hãy tính xem, số điểm tối đa Tí có thể đạt là bao nhiêu?

Input

• Dòng đầu chứa hai số nguyên dương ~n~ và ~k~;
• Dòng thứ hai chứa ~n~ số nguyên dương ~d_1, d_2, …, d_n~.

Giới hạn:

• ~1 ≤ n, k ≤ 25; 1 ≤ d_1, d_2, …, d_n ≤ 1000~.

Output

• Một số nguyên duy nhất là số điểm tối đa Tí có thể đạt được.

Sample

Input #1

5 2
7 3 3 9 10

Output #1

12

Hint

Xét #1: Tí chọn làm các bài số ~2~ và số ~4~, số điểm đạt được là ~3 + 9 = 12~.

Problem source: Chuyên Sơn La Online Judge