1. Phát biểu bài toán

Đoàn tàu gồm ~N~ khoang xếp liên tiếp từ 1 đến ~N~. Khoang thứ ~i~ có hệ số cộng hưởng năng lượng là ~A_i \in \mathbb{Z}~ (có thể âm, bằng 0, hoặc dương) và chi phí khởi tạo biên trái/phải lần lượt là ~L_i, R_i \in \mathbb{Z}_{\ge 0}~.

Một trường giam cầm lượng tử được định nghĩa là một đoạn chỉ số liên tiếp ~[l, r]~ (~1 \le l \le r \le N~). Khi kích hoạt một trường ~[l, r]~, nó đóng góp vào hệ thống một lượng năng lượng ròng là:

$$ E(l, r) = \sum_{i=l}^r A_i - L_l - R_r $$

Hệ thống cần kích hoạt một tập hợp ~\mathcal{F} = \{I_1, I_2, \dots, I_k\}~ gồm đúng ~k~ trường giam cầm đôi một phân biệt (~I_u \ne I_v~ với mọi ~u \ne v~) thỏa mãn ba tiên đề cấu trúc:

1. Tiên đề Phân cấp Laminar: Với hai trường bất kỳ ~I_u = [l_u, r_u]~ và ~I_v = [l_v, r_v]~ thuộc ~\mathcal{F}~, chúng hoặc phải rời nhau hoàn toàn (~[l_u, r_u] \cap [l_v, r_v] = \emptyset~), hoặc một trường phải chứa trọn vẹn trường kia (~[l_u, r_u] \subset [l_v, r_v]~ hoặc ~[l_v, r_v] \subset [l_u, r_u]~).
2. Tiên đề Không suy biến biên: Không có hai trường nào trong ~\mathcal{F}~ được phép có cùng điểm đầu trái hoặc cùng điểm đầu phải (tức là ~l_u \ne l_v~ và ~r_u \ne r_v~ với mọi ~u \ne v~).
3. Tiên đề Quá tải Tầng: Mỗi khoang ~i \in \{1, \dots, N\}~ chỉ được phép nằm trong tối đa ~M~ trường thuộc ~\mathcal{F}~ (tức là ~|\{I \in \mathcal{F} \mid i \in I\}| \le M~).

Yêu cầu: Cho trước số nguyên dương ~K~ và giới hạn tầng ~M~. Với mọi giá trị ~k~ từ 1 đến ~K~, hãy tìm tổng năng lượng ròng lớn nhất ~\sum_{I \in \mathcal{F}} E(I)~ khi kích hoạt đúng ~k~ trường thỏa mãn cả ba tiên đề (nếu với một số ~k~ không tồn tại tập ~\mathcal{F}~ nào có kích thước ~k~ thỏa mãn, in ra từ khóa IMPOSSIBLE).

2. Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên dương ~N, K, M~ (~2 \le N \le 5 \cdot 10^4~; ~1 \le K \le \lfloor N/2 \rfloor~; ~1 \le M \le N~).
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \dots, A_N~ (~|A_i| \le 10^9~).
• Dòng thứ ba chứa ~N~ số nguyên không âm ~L_1, L_2, \dots, L_N~ (~0 \le L_i \le 10^9~).
• Dòng thứ tư chứa ~N~ số nguyên không âm ~R_1, R_2, \dots, R_N~ (~0 \le R_i \le 10^9~).

3. Kết quả

In ra trên một dòng ~K~ giá trị cách nhau bởi khoảng trắng, giá trị thứ ~k~ là tổng năng lượng ròng lớn nhất khi chọn đúng ~k~ trường (hoặc in từ khóa IMPOSSIBLE nếu không thể chọn đủ ~k~ trường).

4. Ví dụ

Ví dụ 1:

• Input:

4 2 1
1 -2 4 3
0 0 0 0
0 0 0 0

• Output:

7 8

Ví dụ 2:

• Input:

4 2 2
1 2 3 4
0 0 0 0
0 0 0 0

• Output:

10 15

5. Subtasks

• Subtask 1 (15% số điểm): ~N \le 80, M = 1~.
• Subtask 2 (25% số điểm): ~M = 1, N \le 3000~.
• Subtask 3 (25% số điểm): ~M \le 3, N \le 5 \cdot 10^4~.
• Subtask 4 (35% số điểm): Không có ràng buộc gì thêm (~N \le 5 \cdot 10^4, M \le N~).