Độ cân bằng

Tuấn có một bộ bài gồm \(n\) quân bài được trải ra thành một dãy từ trái sang phải, trên mỗi quân bài ghi một số nguyên là giá trị của quân bài đó. Giá trị của \(n\) quân bài lần lượt theo dãy trải ra là \(A_1, A_2, \ldots, A_n\). Tuấn định nghĩa các khái niệm sau:

• Đoạn con: Một chuỗi các quân bài liên tiếp nhau trong dãy \(n\) quân bài ban đầu.
• Trọng số của một đoạn con: Là tổng các giá trị của các quân bài trong đoạn đó.
• Độ cân bằng của bộ bài: Là trọng số lớn nhất của bất kỳ đoạn con nào trong dãy \(n\) quân bài. Lưu ý, dãy con rỗng không được tính hợp lệ.

Tuấn mời Tú đến nhà chơi bài và yêu cầu Tú tính độ cân bằng của bộ bài theo định nghĩa trên. Sau khi Tú tính xong, Tuấn tiếp tục thách đố Tú bằng cách yêu cầu chỉnh sửa giá trị một số quân bài để đạt được độ cân bằng cao nhất với các nguyên tắc chỉnh sửa như sau:

• Ban đầu, Tuấn cung cấp thêm một dãy \(n\) số nguyên \(B_1, B_2, \ldots, B_n\).
• Tú có tối đa \(k\) lượt chỉnh sửa. Trong mỗi lượt chỉnh sửa, Tú được phép chọn một đoạn con từ vị trí \(\ell\) đến vị trí \(r\) \((1 \leq \ell \leq r \leq n)\) và thực hiện phép gán:
  \(A_i = A_i \cdot B_i\) với \(i\) thuộc \([l,r]\).

Yêu cầu:
Hãy tính và đưa ra độ cân bằng lớn nhất có thể đạt được sau tối đa \(k\) lượt chỉnh sửa.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \((1 \leq n \le 10^5, \; 0 \le k \leq 10)\), lần lượt là số lượng quân bài và số lượt chỉnh sửa tối đa.
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, \ldots, A_n\) \((-10^6 \leq A_i \leq 10^6)\), biểu diễn giá trị ban đầu của các quân bài.
• Dòng thứ ba chứa \(n\) số nguyên \(B_1, B_2, \ldots, B_n\) \((-10 \leq B_i \leq 10)\), biểu diễn hệ số nhân cho mỗi quân bài.

Output

In ra một số nguyên duy nhất, là độ cân bằng lớn nhất có thể đạt được sau tối đa \(k\) lượt chỉnh sửa.

Example

5 1
-3 4 -5 2 -2
1 -2 -1 2 1

13

3 0
-4 -10 -8
2 2 -1

-4

Scoring

• \(15\%\) số test ứng với \(k = 0\) (không có lượt chỉnh sửa nào).
• \(15\%\) số test ứng với \(k = 1\) và \(n \leq 5000\).
• \(20\%\) số test khác ứng với \(k = 1\).
• \(25\%\) số test khác ứng với \(k = 2\).
• \(25\%\) số test còn lại không có ràng buộc gì thêm.