Trong học kỳ 3 của năm nhất tại trường trung học JOI, học sinh học \(N\) môn trong \(M\) tuần, từ tuần 1 đến tuần \(M\). Các môn được đánh số từ \(1\) đến \(N\). Mỗi tuần có \(N\) tiết học; tiết thứ \(i\) (\(1 \le i \le N\)) dạy môn \(i\).

Trong mỗi tiết trong tổng số \(N \times M\) tiết học, học sinh Bitaro có thể thực hiện một trong hai hành động:

• Hành động 1: Tham dự tiết học theo thời khóa biểu. Nếu tham dự một tiết môn \(i\), mức độ hiểu biết của cậu về môn đó tăng \(A_i\).
• Hành động 2: Không tham dự tiết học theo thời khóa biểu, mà tự chọn một môn bất kỳ để tự học. Nếu tự học môn \(i\) trong một tiết, mức độ hiểu biết của cậu về môn đó tăng \(B_i\).

Ban đầu, mức độ hiểu biết của Bitaro về mọi môn đều bằng \(0\). Sau giờ học, cậu muốn dành thời gian luyện lập trình thi đấu, nên không học thêm ngoài các tiết học này.

Khi học kỳ 3 kết thúc, Bitaro sẽ làm bài thi cuối kỳ. Cậu không muốn bị điểm thấp trong bài thi này, nên muốn mức độ hiểu biết của môn mà mình hiểu ít nhất tại thời điểm thi lớn nhất có thể.

Cho thời khóa biểu và lượng tăng mức độ hiểu biết, hãy tìm giá trị lớn nhất có thể của mức độ hiểu biết nhỏ nhất trong tất cả các môn khi kỳ thi diễn ra.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng:

N M
A_1 A_2 ... A_N
B_1 B_2 ... B_N

Tất cả các giá trị đầu vào đều là số nguyên.

Dữ liệu ra

In ra một dòng chứa giá trị lớn nhất có thể của mức độ hiểu biết nhỏ nhất trong các môn khi kỳ thi diễn ra.

Ràng buộc

• \(1 \le N \le 300\,000\).
• \(1 \le M \le 1\,000\,000\,000\).
• \(1 \le A_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).
• \(1 \le B_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).

Phân nhóm

• Nhóm 1 (10 điểm): \(M=1\).
• Nhóm 2 (25 điểm): \(N \times M \le 300\,000\), \(A_i=B_i\) với mọi \(1 \le i \le N\).
• Nhóm 3 (27 điểm): \(N \times M \le 300\,000\).
• Nhóm 4 (29 điểm): \(A_i=B_i\) với mọi \(1 \le i \le N\).
• Nhóm 5 (9 điểm): Không có ràng buộc bổ sung.

Ví dụ

3 3
19 4 5
2 6 2

18

2 1
9 7
2 6

7

5 60000
630510219 369411957 874325200 990002527 567203997
438920902 634940661 593780254 315929832 420627496

41397427274960

4 25
1 2 3 4
1 2 3 4

48

Nguồn

JOI 2021/2022, vòng chung kết, ngày 13/02/2022. Đề gốc của Ủy ban Olympic Tin học Nhật Bản: tiếng Nhật, tiếng Anh. Bản dịch theo giấy phép CC BY-SA 4.0.