codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

387B.md (2622B)


      1 Source: https://codeforces.com/problemset/problem/387/B
      2 
      3 B. George and Round
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 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 *b**i*.
     22 
     23 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 *a*1, at least one with complexity exactly *a*2, ..., and at least one with complexity exactly *a**n*. Of course, the round can also have problems with other complexities.
     24 
     25 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.
     26 
     27 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.
     28 
     29 Input
     30 
     31 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 *a*1, *a*2, ..., *a**n* (1 ≤ *a*1 < *a*2 < ... < *a**n* ≤ 106) — the requirements for the complexity of the problems in a good round. The third line contains space-separated integers *b*1, *b*2, ..., *b**m* (1 ≤ *b*1 ≤ *b*2... ≤ *b**m* ≤ 106) — the complexities of the problems prepared by George.
     32 
     33 Output
     34 
     35 Print a single integer — the answer to the problem.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 3 5  
     43 1 2 3  
     44 1 2 2 3 3
     45 ```
     46 
     47 Output
     48 
     49 ```
     50 0
     51 ```
     52 
     53 Input
     54 
     55 ```
     56 3 5  
     57 1 2 3  
     58 1 1 1 1 1
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 2
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 3 1  
     71 2 3 4  
     72 1
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 3
     79 ```
     80 
     81 Note
     82 
     83 In the first sample the set of the prepared problems meets the requirements for a good round.
     84 
     85 In the second sample, it is enough to come up with and prepare two problems with complexities 2 and 3 to get a good round.
     86 
     87 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, 4.