DEMCAP3


Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 493M

Problem type

Một làng quê có m chàng trai đánh số từ 1 tới m và 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 số lượng 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 (1 ≤ n, m ≤10^5);

  • Dòng thứ hai chứa m số nguyên dương a[1], a[2], …, a[m] (a[i] ≤ 10^9, i = 1, 2, …, m);

  • Dòng thứ ba chứa n số nguyên dương b[1], b[2], …, b[n] (b[j] ≤ 10^9, j = 1,2,…,n).

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.

Sample Input

3 2
1 2 3
2 3

Sample output

1

Comments

There are no comments at the moment.