AIOC Banner

Problem: Hiring Monks

Want to try solving this problem? You can submit your code online if you log in or register.


Hiring Monks

Input File: hirein.txt
Output File: hireout.txt
Time Limit: 1 second
Memory Limit: 1 GB

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?

Input

Output

Your program should output a single integer: the maximum number of monks who can be assigned to jobs.

Sample Input 1

5
100
300
20
40
1000
2
50
110
3
300
2500
600

Sample Output 1

4

Sample Input 2

4
10
10
20
20
3
15
100
100
0

Sample Output 2

3

Explanation

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.

Subtasks & Constraints

For all cases:

Furthermore:

 


Privacy statement
© Australian Mathematics Trust 2001-2024

Contact: training@orac.amt.edu.au
Page generated: 29 March 2024, 11:17pm AEDT