296
魔獸
貪心-Code forces -387B -George and Round
Code forces -387B -George and Round
description
George decided to prepare a Codesecrof round, so he has prepared m problems for the round. Let's number the problems with integers 1 through m. George estimates the i-th problem's complexity by integer bi.
To make the round good, he needs to put at least n problems there. Besides, he needs to have at least one problem with complexity exactly a1, at least one with complexity exactly a2, ..., and at least one with complexity exactly an. Of course, the round can also have problems with other complexities.
George has a poor imagination. It's easier for him to make some already prepared problem simpler than to come up with a new one and prepare it. George is magnificent at simplifying problems. He can simplify any already prepared problem with complexity c to any positive integer complexity d (c ≥ d), by changing limits on the input data.
However, nothing is so simple. George understood that even if he simplifies some problems, he can run out of problems for a good round. That's why he decided to find out the minimum number of problems he needs to come up with in addition to the m he's prepared in order to make a good round. Note that George can come up with a new problem of any complexity.
Input
The first line contains two integers n and m (1 ≤ n, m ≤ 3000) — the minimal number of problems in a good round and the number of problems George's prepared. The second line contains space-separated integers a1, a2, ..., an (1 ≤ a1 < a2 < ... < an ≤ 106) — the requirements for the complexity of the problems in a good round. The third line contains space-separated integers b1, b2, ..., bm (1 ≤ b1 ≤ b2... ≤ bm ≤ 106) — the complexities of the problems prepared by George.
Output
Print a single integer — the answer to the problem.
Sample Input
3 5
1 2 3
1 2 2 3 3
3 5
1 2 3
1 1 1 1 1
3 1
2 3 4
1
Sample Output
0
2
3
大意：喬治要為比賽命題，共n道，每道題的複雜度給出。他自己已經準備好了m道題，複雜度也給出。若命題的複雜度不低於要求的複雜度，則認為此題合格。
問：喬治盡可能多的用自己的題，那麼他最少還得出幾道新題？
分析：盡量多用已有的題，就要求對自己的題按複雜度由低到高排序，從頭到尾遍曆，若能用則用（貪心）。對要求的題也排序是為了便於比較。
最後更新：2017-04-03 12:56:35