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 đó. Gọ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, ..., A_n\). Tuấn đưa ra các định nghĩa như sau:

• Một đoạn con là 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ố của đoạn con có trọng số lớn nhất trong dãy \(n\) quân bài.

Tuấn rủ 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 đố Tú chỉnh sửa một số giá trị quân bài để bộ bài đạt độ cân bằng cao nhất với các nguyên tắc chỉnh sửa như sau:

• Đầu tiên, Tuấn đưa cho Tú một dãy \(n\) số nguyên \(B_1, B_2, \dots, B_n\);
• Có tối đa \(k\) lượt chỉnh sửa, mỗi lượt Tú được phép chọn một đoạn con các phần tử từ vị trí thứ \(l\) đến vị trí thứ \(r\) (\(1 \le l \le r \le n\)) và thực hiện phép gán \(A_i = A_i \cdot B_i\) với \(\forall i \in [l, r]\).

Yêu cầu: Hãy giúp Tú đưa ra được độ cân bằng lớn nhất với 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 \le n \le 10^5\); \(0 \le k \le 10\)).
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, ..., A_n\) (\(|A_i| \le 1000\)).
• Dòng thứ ba chứa \(n\) số nguyên \(B_1, B_2, ..., B_n\) (\(|B_i| \le 10\)).

Output

• Ghi ra một số nguyên duy nhất là độ cân bằng lớn nhất tìm được của bộ bài sau khi sử dụng 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

• Có \(15\%\) số test ứng với \(k = 0\).
• Có \(15\%\) số test khác ứng với \(k = 1\) và \(n \le 5000\).
• Có \(20\%\) số test khác ứng với \(k = 1\).
• Có \(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.