Thành phố JOI có một con đường đủ dài, có thể xem như một trục số; mỗi vị trí trên đường được biểu diễn bằng một tọa độ thực. Có \(N\) cơ sở nằm dọc theo con đường, được đánh số từ \(1\) đến \(N\) theo thứ tự tọa độ tăng dần. Cơ sở \(i\) (\(1 \le i \le N\)) nằm tại tọa độ \(A_i\).

Thành phố sắp tiến hành kiểm tra an toàn các cơ sở. Cơ sở \(i\) có \(B_i\) hạng mục cần kiểm tra. Có \(K\) người thợ mộc được tập hợp để thực hiện việc kiểm tra. Khi bắt đầu, tất cả họ đều ở tọa độ \(0\). Trong mỗi phút, mỗi người thợ có thể thực hiện một trong hai hành động sau:

• Di chuyển một khoảng cách bằng \(1\) dọc theo trục số.
• Chọn một hạng mục của cơ sở tại tọa độ hiện tại và kiểm tra hạng mục đó.

Khi kết thúc, mọi hạng mục của mọi cơ sở phải được ít nhất một người thợ kiểm tra.

Cho số người thợ và thông tin về các cơ sở, hãy viết chương trình tìm số phút ít nhất cần thiết để hoàn tất việc kiểm tra an toàn.

Dữ liệu vào

Dòng thứ nhất chứa hai số nguyên \(N, K\).

Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\).

Dòng thứ ba chứa \(N\) số nguyên \(B_1, B_2, \ldots, B_N\). Các số trên cùng một dòng được cách nhau bởi dấu cách.

Dữ liệu ra

In ra trên một dòng số phút ít nhất cần thiết để hoàn tất việc kiểm tra an toàn.

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(1 \le K \le 10^9\).
• \(1 \le A_i \le 10^9\) với mọi \(1 \le i \le N\).
• \(A_i < A_{i+1}\) với mọi \(1 \le i \le N-1\).
• \(1 \le B_i \le 10^9\) với mọi \(1 \le i \le N\).
• Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi phân nhóm đều thỏa mãn các ràng buộc chung ở trên.

1. (3 điểm) \(K=1\).
2. (15 điểm) \(K=2\).
3. (82 điểm) Không có ràng buộc bổ sung.

Ví dụ

3 3
1 3 4
4 2 4

7

6 1
1 4 5 6 11 15
12 5 9 8 10 4

63

6 2
1 4 5 6 11 15
12 5 9 8 10 4

35

6 5
1 4 5 6 11 15
12 5 9 8 10 4

19

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.