Snowball Fight 2

Time limit1sMemory limit1024 MB

Summary

Given two increasing lists of snowball sizes thrown by Sweden and Finland, find the maximum number of throws that could have been responses in self-defense.

Level: Medium5 of 10
Topics: Greedy, Two pointers, Dynamic programming, Binary search
Solved: No attempts yet

Problem

During the IOI, Sweden and Finland have a snowball fight with each other. It goes as follows:

One of the countries, say Finland, throws a snowball at the other.
Sweden then answers by throwing an even bigger snowball back (in self-defense).
Which makes Finland also throw a bigger snowball back.
... and so it continues until some country misses (which can happen already on the first throw).
Everything then starts over, possibly with a smaller snowball and a different country throwing it.

After the snowball fight is over, the team leaders of some of the other countries come to the site. They see the remains of thrown snowballs on the ground and are horrified by the amounts. This must go to the next IOI board meeting! Someone suggests a Swedish-Finnish candy ban during the competition as punishment. Sweden and Finland defend themselves: it was only self-defense!

Given the sizes of the snowballs thrown in the different directions, how many of them could at most have been thrown in self-defense?

Input

The first line contains two integers $N$ and $M$ , $1 \le N,M \le 100\,000$ . The second line contains $N$ integers $a_i$ ( $1 \le a_i \le 1\,000\,000$ ): the sizes of the snowballs Sweden threw. The third line contains $M$ integers $b_i$ ( $1 \le b_i \le 1\,000\,000$ ): the sizes of the snowballs Finland threw.

Both sequences are given in increasing order.

Output

Print one integer: the maximum number of snowballs that could have been thrown in self-defense.

Hint

In the first example, Sweden has thrown four snowballs, of sizes 1, 3, 4, and 5 respectively, and Finland has thrown two snowballs of sizes 2 and 3.

It could, for example, have happened by Sweden starting to throw a snowball of size 1 at Finland, who in self-defense throws back one of size 2, whereupon Sweden answers with one of size 3 and misses. Finland then throws its remaining snowball of size 2, and Sweden answers with one of size 4, and misses again. Sweden also misses with its last snowball of size 5. In total, 3 of the snowballs were thrown in self-defense.

In the second example, none of the snowballs could have been in self-defense, since such a snowball must be bigger than the previous one.

Examples2

Example 1
Input
```
4 2
1 3 4 5
2 3
```
Expected output
```
3
```
Example 2
Input
```
3 3
1 1 1
1 1 1
```
Expected output
```
0
```