Cho dãy số nguyên dương \(A_1, A_2, \dots, A_N\) và một số nguyên dương \(K\).

Hãy chọn ra một dãy con gồm \(M\) phần tử (không nhất thiết liên tiếp) từ dãy \(A\), ký hiệu là \(A_{i_1}, A_{i_2}, \dots, A_{i_M}\) với \(1 \le i_1 < i_2 < \dots < i_M \le N\) thỏa mãn đồng thời các điều kiện sau:

1. Chênh lệch chỉ số giữa các phần tử liên tiếp được chọn trong dãy ban đầu không vượt quá \(K\). Nói cách khác, \(i_{j+1} - i_j \le K\) với mọi \(1 \le j < M\).
2. Số lượng số chẵn được chọn trong dãy con bằng đúng số lượng số lẻ được chọn trong dãy con (tức là số lượng số chẵn và số lẻ trong dãy con là bằng nhau. Điều này cũng kéo theo \(M\) phải là một số chẵn và không rỗng, tức là \(M \ge 2\)).
3. Tổng giá trị của các phần tử được chọn \(\sum_{j=1}^M A_{i_j}\) đạt giá trị lớn nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(1 \le K < N \le 3000\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)).

Dữ liệu ra

• In ra một số nguyên duy nhất là tổng lớn nhất của dãy con thỏa mãn yêu cầu đề bài. Nếu không thể tìm được dãy con nào thỏa mãn các điều kiện trên, in ra \(-1\).

Chấm điểm

• Subtask duy nhất (100% số điểm): \(N \le 3000, K \le 3000\).

Ví dụ

5 2
1 4 2 3 5

14