Avatar

Xem PDF



Tác giả:
Dạng bài
Điểm: 100 Thời gian: 2.5s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Pandora là một hành tinh xanh xinh đẹp, là nơi cư ngụ của chủng tộc người Navi. Một ngày đẹp trời, bọn người Trời đến từ trái đất xa xôi quyết định đem các khí tài quân sự hiện đại nhằm xâm lược hành tinh này.

\(n\) robot, robot thứ \(i\) có lượng máu là \(a[i]\), có \(m\) dũng sĩ Navi, dũng sĩ Navi thứ \(j\) có sức tấn công là \(b[j]\). Người Navi rất tôn sùng tín ngưỡng của mình, họ yêu chuộng hòa bình nên mỗi dũng sĩ Navi chỉ có thể tấn công một robot duy nhất. Dũng sĩ Navi thứ \(j\) được coi là tiêu diệt được robot thứ \(i\) nếu như \(b[j] \ge a[i]\).

Hãy tính xem các dũng sĩ Navi có thể tiêu diệt được nhiều nhất bao nhiêu robot?

Input

  • Dòng đầu tiên ghi 2 số nguyên \(n\)\(m\) \((1 \le n,m \le 10^6)\)
  • Dòng thứ hai ghi \(n\) số, với số \(a[i]\) là lượng máu của robot thứ \(i\) \((1 \le i \le n\)\(1 \le a[i] \le 10^9)\)
  • Dòng thứ ba ghi \(m\) số, với số \(b[j]\) là sức tấn công của người Navi thứ \(j\) \((1 \le j \le m\)\(1 \le b[j] \le 10^9)\)

Output

Số lượng Robot nhiều nhất mà các chiến binh Navi có thể tiêu diệt được (Lưu ý: mỗi chiến binh Navi chỉ tấn công một robot duy nhất)

Subtask

  • Subtask \(1\) (\(10\%\) số điểm): \(a[i] = b[j] = 1\ (1 \le i \le n, 1 \le j \le m)\)
  • Subtask \(2\) (\(30\%\) số điểm): \(b[1] = b[2] = \dots = b[n]\)
  • Subtask \(3\) (\(60\%\) số điểm): Không có ràng buộc gì thêm

Sample

Test 1

Input
3 2
1 2 3
1 1
Output
1
Note

Một trong hai chiến binh có thể tiêu diệt robot thứ \(1\) (vì cả ba đều có số máu là \(1\)). Những robot còn lại có quá nhiều máu.


Bình luận

Không có bình luận nào.