Sereja và các phép đổi chỗ

Cho một mảng $a$ gồm $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Với một mảng bất kỳ, ta định nghĩa giá trị $m(a)$ là tổng lớn nhất của một đoạn con liên tiếp không rỗng:

$$m(a)={max}_{1\le i\le j\le n}(a_i+a_{i+1}+\cdots +a_j)$$

Một thao tác đổi chỗ (swap) gồm: chọn hai chỉ số $i\ne j$ rồi hoán đổi giá trị của $a_i$ và $a_j$.

Bạn được phép thực hiện nhiều nhất $k$ thao tác đổi chỗ. Hãy tìm giá trị $m(a)$ lớn nhất có thể đạt được.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• In ra một số nguyên duy nhất là giá trị $m(a)$ lớn nhất có thể đạt được sau khi thực hiện không quá $k$ thao tác đổi chỗ.

Ràng buộc

• $1\le n\le 200$
• $1\le k\le 10$
• $-1000\le a_i\le 1000$

Ví dụ