箱と鍵 (Boxes and Keys)
Unrated
日本語
Language
Contribute a translation- Time limit
- 2000 ms
- Memory limit
- 1024 MB
- Submissions
- 0
- Correct
- 0
- Solved by
- 0
- AC rate
- —
Statement
ビーバーのビ太郎は，鍵のかかった \(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\) が書かれた鍵を使うことで解錠できる．同じ鍵を使って複数の宝箱を解錠してもよい．
ビ太郎は，できるだけ多くの宝箱を解錠したい．ビ太郎が解錠できる宝箱の個数の最大値を求めよ．
Constraints
- \(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\))．
- 入力される値はすべて整数である．
Input
入力は以下の形式で標準入力から与えられる．
\(N\) \(M\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
\(B_1\) \(B_2\) \(\cdots\) \(B_M\)
Output
ビ太郎が解錠できる宝箱の個数の最大値を出力せよ．
Examples
Sample input 1
4 4 2 2 3 1 2 1 4 1
Sample output 1
3
- 宝箱 \(1\) には整数 \(2\) が書かれている．鍵 \(1\) にも整数 \(2\) が書かれている．よって，宝箱 \(1\) は鍵 \(1\) を使うことで解錠できる．
- 宝箱 \(2\) は鍵 \(1\) を使うことで解錠できる．
- 宝箱 \(3\) はどの鍵を使っても解錠できない．
- 宝箱 \(4\) は鍵 \(2\) や鍵 \(4\) を使うことで解錠できる．
したがって，ビ太郎は最大で \(3\) 個の宝箱を解錠できる．
Sample input 2
5 3 1 1 1 1 1 1 1 1
Sample output 2
5
Sample input 3
10 11 7 447 71 130 24 1 2 221 71 1334 14 93 2000 204 447 221 7 101 7 1 30
Sample output 3
4
Notes
JOI 2022 · JCIOI · CC BY-SA 4.0
Tags
No tags yet