Bus Stop Assignment Under Rain

You are given N bus stops labeled from 1 to \(N\). The \(i\)th bus stop can accommodate at most \(B_i\) people. Between every consecutive bus stops \(i\) and \(i+1\) (for \(1 \le i \le N-1\)) there is an open-air market. The \(i\)th market sells \(U_i\) umbrellas at a price of 1 each, and there are \(P_i\) people in the market. Initially, all bus stops are empty.

When it suddenly starts raining, every person in market \(i\) (\(1 \le i \le N-1\)) must choose one of the following actions:

• Go to bus stop \(i\);
• Go to bus stop \(i+1\);
• Stay in the market and buy an umbrella.

If a person cannot successfully take one of these actions (i.e. if they cannot get on a bus stop due to capacity limits and cannot buy an umbrella because of insufficient supply), they will get wet. Your task is to determine whether it is possible to arrange for every person to avoid getting wet. If it is possible, you must output the minimum total cost (which is the total number of umbrellas purchased, each costing 1) and an assignment for each person indicating which bus stop they move to. For persons who purchase an umbrella, output 0 as their bus stop assignment.

Note: For each market \(i\), if \(x_i\) people go to bus stop \(i\) and \(y_i\) people go to bus stop \(i+1\), then the remaining \(P_i - (x_i+y_i)\) people will buy an umbrella. The following constraints must be met:

• For market \(i\): \(x_i + y_i + z_i = P_i\) with \(z_i \le U_i\) (umbrellas available).
• Bus stop 1: \(x_1 \le B_1\).
• For bus stop \(i\) where \(2 \le i \le N-1\): \(x_i + y_{i-1} \le B_i\).
• Bus stop \(N\): \(y_{N-1} \le B_N\).

The goal is to minimize the total cost, which equals \(\sum_{i=1}^{N-1}(P_i - (x_i+y_i))\). If there is no valid assignment that prevents anyone from getting wet, output -1.

inputFormat

The first line contains an integer \(N\) (the number of bus stops).

The second line contains \(N\) space-separated integers: \(B_1, B_2, \ldots, B_N\) representing the capacities of the bus stops.

Then, for each market \(i\) from 1 to \(N-1\), there is a line containing two space-separated integers: \(U_i\) and \(P_i\) representing the number of umbrellas available at market \(i\) and the number of people in market \(i\), respectively.

outputFormat

If it is impossible to prevent everyone from getting wet, output -1.

Otherwise, on the first line output the minimum total cost (the number of umbrellas purchased). Then, for each market from 1 to \(N-1\), output a line containing \(P_i\) space-separated integers. For each person in market \(i\), output the bus stop number they should go to if they are assigned a bus stop, or 0 if they buy an umbrella.

sample

3
2 3 1
1 3
0 2

0
1 1 2
2 2