Công ty sữa \(Vinamilk\) muốn tặng quà cho mỗi hộ gia đình ở huyện \(A\). Có tất cả \(m\) con bò đực được đánh số từ 1 đến \(m\) và \(n\) con bò cái được đánh số từ 1 đến \(n\). Bò đực thứ \(i\) có cân nặng \(a[i]\) (\(i = 1 -> m\)), bò cái thứ \(j\) có cân nặng \(b[j]\) (\(j = 1 -> n\)). Trong buổi trao quà, ban tổ chức muốn tặng mỗi hộ một cặp bò. Mỗi cặp gồm một con bò đực và một con bò cái, trong đó cân nặng của con bò đực phải lớn hơn cân nặng của con bò cái, mỗi con bò chỉ được ghép cặp một lần.
Hãy viết chương trình tìm ra số cặp nhiều nhất thỏa mãn yêu cầu của ban tổ chức.
Thông số đầu vào
Dòng 1 chứa hai số nguyên dương \(m, n\) (\(m, n \le 10^6\))
Dòng 2 chứa m số nguyên dương \(a[1], a[2],... a[m]\) (\(a[i] \le 10^9\))
Dòng 3 chứa n số nguyên dương \(b[1], b[2],... b[n]\) (\(b[i] \le 10^9\))
Thông số đầu ra
Một số nguyên duy nhất là số cặp nhiều nhất xếp được.
Ví dụ đầu vào 1
3 2
1 2 3
2 3
Ví dụ đầu ra 1
1
Giải thích ví dụ 1
Bò đực thứ 3 ghép với bò cái thứ 1
Ví dụ đầu vào 2
3 3
3 2 5
1 2 3
Ví dụ đầu ra 2
3
Giải thích ví dụ 2
Có thể xếp được nhiều nhất 3 cặp
Bò đực thứ 1 ghép với bò cái thứ 2
Bò đực thứ 2 ghép với bò cái thứ 1
Bò đực thứ 3 ghép với bò cái thứ 3
Ràng buộc
60% số test có \(n + m \le 10^4\)
30% số test có \(n + m \le 5*10^5\)
10% số test cuối không ràng buộc gì thêm
Bình luận