Problem K
Frosh Week
Professor Zac is trying to finish a collection of tasks during the first week at the start of the term. He knows precisely how long each task will take, down to the millisecond. Unfortunately, it is also Frosh Week. Zac’s office window has a clear view of the stage where loud music is played. He cannot focus on any task when music is blaring.
The event organizers are also very precise. They supply Zac with intervals of time when music will not be playing. These intervals are specified by their start and end times down to the millisecond.
Each task that Zac completes must be completed in one quiet interval. He cannot pause working on a task when music plays (he loses his train of thought). Interstingly, the lengths of the tasks and quiet intervals are such that it is impossible to finish more than one task per quiet interval!
Given a list of times $t_ i$ (in milliseconds) that each task will take and a list of times $\ell _ j$ (in milliseconds) specifying the lengths of the intervals when no music is being played, what is the maximum number of tasks that Zac can complete?
Input
The first line of input contains a pair of integers $n$ and $m$, where $n$ is the number of tasks and $m$ is the number of time intervals when no music is played. The second line consists of a list of integers $t_1, t_2, \ldots , t_ n$ indicating the length of time of each task. The final line consists of a list of times $\ell _1, \ell _2, \ldots , \ell _ m$ indicating the length of time of each quiet interval when Zac is at work this week.
You may assume that $1 \leq n,m \leq 200\, 000$ and $100\, 000 \leq t_ i, \ell _ j \leq 199\, 999$ for each task $i$ and each quiet interval $j$.
Output
Output consists of a single line containing a single integer indicating the number of tasks that Zac can accomplish from his list during this first week.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 4 150000 100000 160000 100000 180000 190000 170000 140000 160000 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 4 180000 185000 199999 100000 199999 180000 170000 120000 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 3 199999 180000 170001 199999 170000 180000 |
2 |
