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.

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.