Aoi chuẩn bị \(N\) loại cà ri và \(M\) loại cơm. Loại cà ri \(i\) có \(A_i\) phần, loại cơm \(j\) có \(B_j\) phần. Một phần cà ri và một phần cơm tạo thành một suất cà ri cơm.

Mỗi con hải ly nhận đúng một suất, nhưng không có hai con nào được nhận cùng một loại cà ri cơm. Hai suất chỉ được coi là cùng loại khi cả loại cà ri lẫn loại cơm đều giống nhau. Hãy tìm số hải ly lớn nhất có thể nhận một suất từ nguyên liệu đã chuẩn bị.

Dữ liệu vào

Dòng đầu gồm \(N,M\). Dòng thứ hai gồm \(A_1,A_2,...,A_N\). Dòng thứ ba gồm \(B_1,B_2,...,B_M\).

Dữ liệu ra

In một số nguyên: số suất cà ri cơm lớn nhất có thể phục vụ.

Ràng buộc

• \(1 ≤ N,M ≤ 500000\).
• \(1 ≤ A_i,B_j ≤ 10^9\).
• Mọi giá trị đầu vào là số nguyên.

Phân nhóm

1. \(6\) điểm: mọi \(A_i\) và \(B_j\) bằng \(1\).
2. \(7\) điểm: \(N=M=2\).
3. \(12\) điểm: \(N=2\).
4. \(14\) điểm: \(A_1=A_2=...=A_N\).
5. \(20\) điểm: tổng các \(A_i\) và tổng các \(B_j\) không vượt quá \(2000\).
6. \(19\) điểm: tổng các \(A_i\) và tổng các \(B_j\) không vượt quá \(500000\).
7. \(22\) điểm: không có ràng buộc thêm.

Ví dụ

3 4
2 2 2
4 1 1 1

6

3 4
4 2 4
1 4 3 1

8

2 2
1 1000000000
1000000000 1

3

Nguồn

JOIG 2025/2026 - Chung kết, Cuộc thi 3, bài Curry and Rice.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.