Kích hoạt Nguyên tử

Có $N$ nguyên tử đánh số từ $1$ đến $N$. Ban đầu mọi nguyên tử ở trạng thái bình thường. Kích hoạt nguyên tử $i$ tiêu tốn $D_i$ năng lượng, và khi được kích hoạt nó toả ra $A_i$ năng lượng. Bạn được phép kích hoạt tuỳ ý số nguyên tử (kể cả không kích hoạt nguyên tử nào).

Các nguyên tử liên kết với nhau theo một chiều đặc biệt. Với mỗi $i$ $(1\le i<N)$ tồn tại một liên kết $E_i$: nếu nguyên tử $i$ được kích hoạt thì nguyên tử $E_i$ cũng lập tức được kích hoạt miễn phí (và hiệu ứng này lan truyền tiếp). Ban đầu $E_i=i+1$. Nguyên tử $N$ không có liên kết đi ra.

Trước khi bắt đầu kích hoạt, bạn buộc phải thay đổi đúng $K$ lần liên kết. Mỗi lần thay đổi: chọn một chỉ số $i$ $(1\le i<N)$ và đổi $E_i$ sang một giá trị khác với $i$ và khác với giá trị $E_i$ hiện tại. Một liên kết có thể được giữ nguyên (nếu không chọn nó) hoặc bị đổi nhiều lần.

Sau khi đã thực hiện xong đúng $K$ lần thay đổi, bạn mới được kích hoạt các nguyên tử. Tổng năng lượng thu được bằng tổng $A_i$ trên mọi nguyên tử đang ở trạng thái kích hoạt, trừ đi tổng $D_i$ trên những nguyên tử mà bạn trực tiếp trả chi phí để kích hoạt.

Hãy xác định tổng năng lượng 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òng thứ ba chứa $N$ số nguyên $D_1,D_2,\dots ,D_N$.

Dữ liệu ra

Một số nguyên duy nhất là tổng năng lượng lớn nhất đạt được.

Ràng buộc

• $4\le N\le {10}^5$
• $0\le K<N$
• $1\le A_i\le {10}^6$
• $1\le D_i\le {10}^6$

Ví dụ