During the IOI competition, Sweden and Finland have snowball fights against each other. Each fight goes as follows:
Someone from one of the countries, say Finland, throws a snowball at the other.
Sweden then responds by throwing an even bigger snowball back (in self-defense).
Which makes Finland throw an even bigger snowball back.
â€¦and so it goes, until someone misses (which can happen on the first throw).
Then everything starts over, posssibly with a smaller snowball and another country that throws it.
After the snowball fight is over, the team leaders for the other countries come to where the fight had been. On the ground they see the remains of the snowballs thrown and become terrified of their sizes. This will be brought up a the next IOI board meeting! Someone proposes a ban on sweets for Swedes and Finns during the competition as punishment. Sweden and Finland both protest: the snowballs were only thrown in self-defense!
Given the sizes of the snowballs thrown and their directions, how many of them (at most) could have been thrown in self-defense?
The input describes one snowball fight. The first line contains two numbers $N$ and $M$, $1 \le N,M \le 100\, 000$. The second line contains $N$ numbers $a_ i$ ($1 \le a_ i \le 1\, 000\, 000$): the sizes of the snowballs that Sweden threw. The third line contains $M$ numbers $b_ i$ ($1 \le b_ i \le 1\, 000\, 000$): the sizes of the snowballs that Finland threw.
Both sequences are given in increasing order.
Print one number: the maximum number of snowballs that could have been thrown in self-defense.
In the first sample case Sweden threw four snowballs, of sizes $1$, $3$, $4$, and $5$, and Finland threw two snowballs of sizes $2$ and $3$.
It could be that Sweden began by throwing a snowball of size $1$ at Finland, which in self-defense threw one back of size $2$, and Sweden answered with one of size $3$, which missed.
Finland then threw its remaining snowball of size $3$, and Sweden answered with one of size $4$, and missed again. Sweden also missed with its last snowball of size $5$. There were $3$ total snowballs thrown in self-defense.
In the second sample case no snowballs could have been thrown in self-defense, because such a snowball must be larger than the previous one.
Your solution will be tested on several test case groups. To get points for a group, your solution must pass all the test cases in the group.
Group |
Points |
Bounds |
Other |
$1$ |
$19$ |
$1 \le N,M \le 1\, 000$ |
You can assume that Sweden misses with all the snowballs they throw. |
$2$ |
$23$ |
$1 \le N,M \le 1\, 000$ |
You can assume that Finland always throws the first snowball. |
$3$ |
$20$ |
$1 \le N,M \le 1\, 000$ |
You can assume that no two snowballs have the same size. |
$4$ |
$38$ |
$1 \le N,M \le 100\, 000$ |
Sample Input 1 | Sample Output 1 |
---|---|
4 2 1 3 4 5 2 3 |
3 |
Sample Input 2 | Sample Output 2 |
---|---|
3 3 1 1 1 1 1 1 |
0 |