High up in the peaks of Kosciuszko National Park, an elite sect of monks are deciding how to assign jobs to the new monks.
They have hired N new monks, numbered from 1 to N, each possessing a possibly different skill level. The monk i has a skill level of xi.
There are S student jobs available, numbered from 1 to S, created for monks to learn from their masters. As such, there is a limit on how much skill a monk can have for this job. Student job j is available to monks with a skill level at most sj.
There are M master jobs available, numbered from 1 to M, created for monks to teach their students. As such, there is a minimum skill level a monk must have for this job. Master job k is available to monks with a skill level at least mk.
Each monk can be assigned at most one job, and each job can be assigned to at most one monk. What is the largest number of monks you can assign to jobs?
Your program should output a single integer: the maximum number of monks who can be assigned to jobs.
5 100 300 20 40 1000 2 50 110 3 300 2500 600
4 10 10 20 20 3 15 100 100 0
In the first sample input, one way you can assign the monks is as follows:
This assigns four monks, which is the maximum possible.
In the second sample input, one way you can assign the monks is as follows:
This assigns three monks, which is the maximum possible.
For all cases:
For Subtask 1 (15 marks), sj = 10, for all j, and mk = 10, for all k.
Hint: This subtask says the skill level limit for student jobs, and the minimum skill level for master jobs, is always 10. This means the only thing that matters about each monk, is whether their skill is less than 10, more than 10, or equal to 10.
For Subtask 2 (15 marks), sj = 200, for all j, and mk = 100, for all k.
Hint: The solution to this subtask is quite similar to Subtask 1.
For Subtask 3 (30 marks), S = 0, N ≤ 1000 and M ≤ 1000. In particular, S = 0 means that there are no student jobs; there are only master jobs.
Hint: To start with, ask yourself which monk should be assigned to the master job requiring the most skill.
For Subtask 4 (20 marks), S = 0. There are no student jobs; there are only master jobs.
Hint: The input is quite large in this subtask, so you will need a fast solution. Try to avoid nested loops. Maybe sorting will help?
For Subtask 5 (20 marks), no further constraints apply.
There are no hints available for this subtask.