Trips
Memory limit: 64 MB
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.
Task
Write a program, that:
-
reads the description of the groups and the trips from
the standard input,
-
matches the groups and trips in such a way, that the
maximum number of arranged trips is reached,
-
writes the result to standard output.
If there are several possible solutions, your program should
output anyone of them.
Input
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,
.
Output
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.
Example
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.