In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
In the forthcoming holiday season, a lot of people would like to go for an unforgettable travel. To mostly enjoy their journey, everyone wants to go with a group of friends. A travel agency offers several trips. A travel agency offers group trips, but for each trip, the size of the group is limited: the minimum and maximum number of persons are given. Every group can choose only one trip. Moreover, each trip can be chosen by only one group. The travel agency has asked you for help. They would like to organize as many trips as possible. Your task is to match groups of people and trips in such a way, that the maximum number of trips can be organized.
Write a program, that:
The first line of input contains two integers: and separated by single space, , ; is the number of groups and is the number of trips. The groups are numbered from 1 to , and the trips are numbered from 1 to .
The following lines contain group sizes, one per line. Line contains integer - the size of the -th group, .
The following lines contain trip descriptions, one trip per line. Line contains two integers: and , separated by single space. is the minimum, and is the maximum size of a group for which the trip can be arranged, .
The first line of output should contain one integer - the maximum number of trips that can be arranged. The following lines should contain the description of the matching. Each of these lines should contain a pair of integers separated by single space: the number of a group and the number of a trip. There can be many answers and your program may print anyone of them.
For the input data:
5 4 54 6 9 42 15 6 6 20 50 2 8 7 20
the correct result is:
3 2 1 3 4 4 2
Task author: Krzysztof Sikora.