Problem G. Group by the bus

Author:M. Sporyshev   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

N delegations arrived for the ACM ICPC quarterfinals. Delegation i consists of ai people.

The organizers were able to find M buses to deliver the contestants from the hotel to the university. Bus j has enough place for bj people.

Settling the delegations into buses was entrusted to Masha — the most responsible member of the organizing committee. However, that was done in the very last day, which resulted in the following:

Contestants from each delegation prefer to stay together. But unfortunately some delegations may have to split into groups to fit into the buses. Masha wants to help the teams to form the least number of groups that will fit in the buses, given the constraints above (if a delegation is not split, it counts as 1 group).

Your program must allocate bus seats to contestants in a way which minimizes number of groups. It's guaranteed that total amount of people is not more than total capacity of the buses.

Input file format

Input file contains an integer N — number of delegations, followed by N integers ai — sizes of delegations in the order they queue at the bus stop.

Further follows an integer M — number of buses, followed by M integers bj — capacities of the buses in the order they arrive.

Output file format

Output file must contain a description for each delegation from 1 to N, in the same order as input.

A description for delegation i starts with a positive integer pi — the number of groups that the delegation is split into (1 means the delegation is not split at all).

Further, pi pairs of positive integers must follow. The first integer of each pair is the number of the bus that the group should take (buses are numbered from 1 to M). The second integer is the size of the group. Groups within one delegation should be described in the order of ascending bus numbers.

The number of groups in the output should be minimal possible, given the constrains above. If there is more than one optimal solution, output any of them.

In the sample test #1 there are 3 delegations and 2 buses. The answer contains 4 groups in total (we have to split delegation 2 into 2 groups).

In the sample test #2 the second bus can fit both delegations, no splits required. Note that the first bus leaves completely empty.

Constraints

1 ≤ N, M, ai, bj ≤ 100

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
2 4 1
2
4 4
1
1 2
2
1 2
2 2
1
2 1
2
2
3 4
2
2 10
1
2 3
1
2 4

0.037s 0.008s 15