CF387B.George and Round

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

George decided to prepare a Codesecrof round, so he has prepared mm problems for the round. Let's number the problems with integers 11 through mm . George estimates the ii -th problem's complexity by integer bib_{i} .

To make the round good, he needs to put at least nn problems there. Besides, he needs to have at least one problem with complexity exactly a1a_{1} , at least one with complexity exactly a2a_{2} , ..., and at least one with complexity exactly ana_{n} . 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 cc to any positive integer complexity dd ( c>=dc>=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 mm he's prepared in order to make a good round. Note that George can come up with a new problem of any complexity.

输入格式

The first line contains two integers nn and mm ( 1<=n,m<=30001<=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,...,ana_{1},a_{2},...,a_{n} ( 1<=a_{1}<a_{2}<...<a_{n}<=10^{6} ) — the requirements for the complexity of the problems in a good round. The third line contains space-separated integers b1,b2,...,bmb_{1},b_{2},...,b_{m} ( 1<=b1<=b2...<=bm<=1061<=b_{1}<=b_{2}...<=b_{m}<=10^{6} ) — the complexities of the problems prepared by George.

输出格式

Print a single integer — the answer to the problem.

输入输出样例

  • 输入#1

    3 5
    1 2 3
    1 2 2 3 3
    

    输出#1

    0
    
  • 输入#2

    3 5
    1 2 3
    1 1 1 1 1
    

    输出#2

    2
    
  • 输入#3

    3 1
    2 3 4
    1
    

    输出#3

    3
    

说明/提示

In the first sample the set of the prepared problems meets the requirements for a good round.

In the second sample, it is enough to come up with and prepare two problems with complexities 22 and 33 to get a good round.

In the third sample it is very easy to get a good round if come up with and prepare extra problems with complexities: 2,3,42,3,4 .

首页