C. DANCE - Khiêu vũ

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản

Đề bài

Một làng quê có m chàng trai đánh số từ 1 tới m n cô gái đánh số từ 1 tới n . Chàng trai thứ i có chiều cao a_i\ (i=1,2,…,m) , cô gái thứ j có chiều cao b_j\ (j=1,2,…,n) .

Trong một buổi khiêu vũ, người ta muốn chọn ra một số cặp nhảy. Mỗi cặp nhảy gồm đúng một chàng trai và một cô gái và trong cặp đó, chàng trai phải cao hơn cô gái. Mỗi chàng trai, cô gái trong làng không được tham gia quá một cặp nhảy.

Yêu cầu: Tìm một số nhiều nhất các cặp nhảy thỏa mãn yêu cầu trên.

Dữ liệu vào:

  • Dòng đầu chứa hai số nguyên dương m,n≤10^5 ;
  • Dòng thứ hai chứa m số nguyên dương a_1,a_2,…,a_m\ (∀i:a_i≤10^9) ;
  • Dòng thứ ba chứa n số nguyên dương b_1,b_2,…,b_n\ (∀j:b_j≤10^9) .

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất là số cặp nhảy theo phương án tìm được.

Ví dụ:

Dữ liệu vào:
3 2
1 2 3
2 3
Dữ liệu ra:
1

Giới hạn:

  • Ít nhất 50\% số điểm ứng với các test có m,n≤1000 .