Đề bài

Sau khi sự nghiệp trộm tranh không hào nhoáng như mong đợi, bạn chuyển sang một mục tiêu mới: lấy trộm một huy chương tại CEOI năm nay. Kế hoạch đang diễn ra thuận lợi, nhưng giai đoạn tiếp theo cần một trợ lý và hiện tại bạn chưa đủ tiền thuê người.

Một cửa hàng ở Berlin bán \(N\) rô-bốt hút bụi có thể lập trình, đánh số từ \(1\) đến \(N\). Rô-bốt \(i\) có giá \(c_i\) euro. Người bán chỉ chấp nhận bán một đoạn liên tiếp đầy đủ: nếu mua rô-bốt \(i\) và \(j\), bạn phải mua mọi rô-bốt \(k\) với \(i\le k\le j\).

Các thí sinh khác rất thích rô-bốt, nên bạn hứa bán cho họ đúng \(K\) chiếc (\(1\le K\le N\)). Họ sẽ trả \(s_i\) euro cho rô-bốt \(i\).

Hãy:

• Tính lợi nhuận lớn nhất có thể đạt được khi mua một đoạn gồm ít nhất \(K\) rô-bốt rồi bán đúng \(K\) rô-bốt trong đoạn đó.
• Xác định những rô-bốt có thể được bán trong ít nhất một giao dịch đạt lợi nhuận lớn nhất.

Lợi nhuận của một giao dịch bằng tổng số tiền nhận được từ \(K\) rô-bốt đã bán trừ tổng giá mua của toàn bộ đoạn rô-bốt.

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 \(c_1,c_2,\ldots,c_N\).

Dòng thứ ba chứa \(N\) số nguyên \(s_1,s_2,\ldots,s_N\).

Dữ liệu ra

Dòng đầu in một số nguyên là lợi nhuận lớn nhất có thể đạt được.

Dòng thứ hai in một xâu nhị phân độ dài \(N\). Ký tự thứ \(i\) là 1 nếu rô-bốt \(i\) có thể được bán trong một giao dịch nào đó đạt lợi nhuận lớn nhất, và là 0 nếu không.

Ràng buộc

• \(1\le N\le250\,000\).
• \(1\le K\le N\).
• \(1\le c_i,s_i\le10^9\) với mọi \(1\le i\le N\).

Phân nhóm

Mỗi subtask gồm hai nhóm. Nhóm thứ nhất cho điểm khi lợi nhuận lớn nhất được tính đúng; nhóm thứ hai cho thêm điểm khi toàn bộ dữ liệu ra, bao gồm xâu nhị phân, đúng.

• Subtask 1 (5 + 5 điểm): \(N\le200\).
• Subtask 2 (5 + 5 điểm): \(N\le6\,000\).
• Subtask 3 (5 + 5 điểm): \(K=2\).
• Subtask 4 (10 + 15 điểm): \(K\le200\).
• Subtask 5 (25 + 20 điểm): Không có ràng buộc bổ sung.

Ví dụ

5 3
3 5 2 3 6
2 1 5 2 3

-1
00111

5 2
1 6 1 5 2
4 1 6 2 4

2
10111