D - 箱と鍵 (Boxes and Keys)
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 100 点
問題文
ビーバーのビ太郎は,鍵のかかった N 個の宝箱と M 個の鍵を手に入れた.N 個の宝箱には 1 から N までの番号が付けられており,宝箱 i (1 \leqq i \leqq N) には整数 A_i が書かれている.M 個の鍵には 1 から M までの番号が付けられており,鍵 j (1 \leqq j \leqq M) には整数 B_j が書かれている.
宝箱 i は整数 A_i が書かれた鍵を使うことで解錠できる.同じ鍵を使って複数の宝箱を解錠してもよい.
ビ太郎は,できるだけ多くの宝箱を解錠したい.ビ太郎が解錠できる宝箱の個数の最大値を求めよ.
制約
- 1 \leqq N \leqq 100.
- 1 \leqq M \leqq 100.
- 1 \leqq A_i \leqq 2\,000 (1 \leqq i \leqq N).
- 1 \leqq B_j \leqq 2\,000 (1 \leqq j \leqq M).
- 入力される値はすべて整数である.
入力
入力は以下の形式で標準入力から与えられる.
N M A_1 A_2 \cdots A_N B_1 B_2 \cdots B_M
出力
ビ太郎が解錠できる宝箱の個数の最大値を出力せよ.
入力例 1
4 4 2 2 3 1 2 1 4 1
出力例 1
3
- 宝箱 1 には整数 2 が書かれている.鍵 1 にも整数 2 が書かれている.よって,宝箱 1 は鍵 1 を使うことで解錠できる.
- 宝箱 2 は鍵 1 を使うことで解錠できる.
- 宝箱 3 はどの鍵を使っても解錠できない.
- 宝箱 4 は鍵 2 や鍵 4 を使うことで解錠できる.
したがって,ビ太郎は最大で 3 個の宝箱を解錠できる.
入力例 2
5 3 1 1 1 1 1 1 1 1
出力例 2
5
入力例 3
10 11 7 447 71 130 24 1 2 221 71 1334 14 93 2000 204 447 221 7 101 7 1 30
出力例 3
4