Problem Description

There are $N$ bus stops, numbered $1, \ldots, N$. The $i$-th bus stop can hold $B_{i}$ people.

For each $i \in \{1, \ldots, N-1\}$, there is a sidewalk connecting bus stop $i$ and bus stop $i+1$, with an open-air market in between. Market $i$ sells $U_{i}$ umbrellas, and each umbrella costs $1$.

Currently, there are $P_{i}$ people in market $i$, and all bus stops are empty.

Suddenly, it starts to rain. Each person in market $i$ must choose one of the following three options:

• Go to bus stop $i$.
• Go to bus stop $i+1$.
• Stay and buy an umbrella.

If a person cannot get into a bus stop or cannot buy an umbrella, they will get wet.

You need to determine whether, under an optimal arrangement, it is possible to ensure that nobody gets wet. If it is possible, you must output the minimum total money that needs to be spent, and where people from each market should go.

Input Format

The first line contains an integer $N$.

The second line contains $N$ space-separated integers $B_{i}\ (1 \leq i \leq N)$, representing the capacity of bus stop $i$.

The third line contains $N-1$ space-separated integers $P_{i}\ (1 \leq i \leq N-1)$, representing the number of people in market $i$.

The fourth line contains $N-1$ space-separated integers $U_{i}\ (1 \leq i \leq N-1)$, representing the number of umbrellas sold in market $i$.

Output Format

If everyone can end up either under an umbrella or in a bus stop, output $N+1$ lines:

• The first line should be YES.
• The second line should be an integer, the minimum total money spent on umbrellas.
• The next $N-1$ lines should each contain three space-separated integers. For market $i\ (1 \leq i \leq N-1)$, they represent: the number of people who move to bus stop $i$, the number of people who buy umbrellas, and the number of people who move to bus stop $i+1$.

If there are multiple valid solutions, you may output any one of them.

Otherwise, output a single line NO.

3
10 15 10
20 20
0 0

NO

3
10 15 10
20 20
0 11

YES
5
10 0 10
5 5 10

Hint

Explanation for Sample 1

There are $35$ empty spots in the bus stops and no umbrellas for sale, but there are $40$ people in the market, so the answer is NO.

Explanation for Sample 2

The $10$ people in market $1$ go to bus stop $1$, nobody buys an umbrella, and $10$ people go to bus stop $2$.

In market $2$, $5$ people go to bus stop $2$, $5$ people stay and buy umbrellas, and $10$ people move to bus stop $3$.

In total, $5$ umbrellas are bought, costing $5$.

Constraints

For all testdata, $2 \leq N \leq 10^{6}$, $0 \leq B_{i} \leq 2 \cdot 10^{9}$, $0 \leq P_{i}, U_{i} \leq 10^{9}$.

Translated by ChatGPT 5