#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <cassert>
#include <algorithm>
using namespace std;
#define int long long
typedef long long ll;
const ll INF = 1e18;
// Edge structure for our min-cost flow graph.
struct Edge {
int to, rev; // 'to' is the destination node, 'rev' is the index of the reverse edge.
ll cap, cost; // 'cap' is the capacity, 'cost' is the cost per unit of flow.
ll orig; // Original capacity (used later to extract the assignment).
};
struct MinCostFlow {
int n; // number of nodes in the graph
vector<vector<Edge>> graph;
vector<ll> dist, potential;
vector<int> parent, parentEdge;
MinCostFlow(int n) : n(n), graph(n), dist(n), potential(n), parent(n), parentEdge(n) { }
// Adds a directed edge from node s to node t with capacity 'cap' and cost 'cost'.
void addEdge(int s, int t, ll cap, ll cost) {
Edge a = { t, (int)graph[t].size(), cap, cost, cap };
Edge b = { s, (int)graph[s].size(), 0, -cost, 0 };
graph[s].push_back(a);
graph[t].push_back(b);
}
// Computes the min-cost flow from s to t, sending at most 'f' units.
// Returns a pair {flow, total cost}.
pair<ll, ll> minCostFlow(int s, int t, ll f) {
ll flow = 0, cost = 0;
// Initialize potentials (for reduced costs) to 0.
fill(potential.begin(), potential.end(), 0);
while (flow < f) {
// Use Dijkstra's algorithm to find the shortest (adjusted) path from s to t.
fill(dist.begin(), dist.end(), INF);
dist[s] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, s});
while(!pq.empty()){
auto [d, v] = pq.top();
pq.pop();
if(d != dist[v]) continue;
for (int i = 0; i < graph[v].size(); i++){
Edge &e = graph[v][i];
if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + potential[v] - potential[e.to]){
dist[e.to] = dist[v] + e.cost + potential[v] - potential[e.to];
parent[e.to] = v;
parentEdge[e.to] = i;
pq.push({dist[e.to], e.to});
}
}
}
if(dist[t] == INF) break; // No path exists; not all flow can be sent.
// Update potentials.
for (int i = 0; i < n; i++){
if(dist[i] < INF)
potential[i] += dist[i];
}
// Determine the maximum additional flow we can send along the path.
ll addFlow = f - flow;
for (int v = t; v != s; v = parent[v]){
addFlow = min(addFlow, graph[parent[v]][parentEdge[v]].cap);
}
flow += addFlow;
cost += addFlow * potential[t];
// Update the capacities along the path.
for (int v = t; v != s; v = parent[v]){
Edge &e = graph[parent[v]][parentEdge[v]];
e.cap -= addFlow;
graph[v][e.rev].cap += addFlow;
}
}
return {flow, cost};
}
};
//
// Main: Reads input, builds the flow network, runs the min-cost flow algorithm, and prints output.
//
// Input Specification:
// - First line: integer N (number of bus shelters).
// - Second line: N space-separated integers B[1..N] (capacity of each bus shelter).
// - Third line: N-1 space-separated integers P[1..N-1] (number of people at market i).
// - Fourth line: N-1 space-separated integers U[1..N-1] (umbrellas available at market i).
//
// Output Specification:
// - If every person can stay dry, output N+1 lines:
// YES
// <minimum umbrella cost>
// For each market i (1 to N-1), output three integers:
// <# going to bus shelter i> <# buying umbrella> <# going to bus shelter i+1>
// - Otherwise, output a single line: NO
//
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<ll> B(N+1);
for (int i = 1; i <= N; i++){
cin >> B[i];
}
int M = N - 1; // Markets are numbered 1..N-1.
vector<ll> P(M+1), U(M+1);
for (int i = 1; i <= M; i++){
cin >> P[i];
}
for (int i = 1; i <= M; i++){
cin >> U[i];
}
// Build our flow network with the following node layout:
// Node 0: Source (S)
// Nodes 1 .. M: Markets (market i is node i)
// Nodes M+1 .. M+N: Bus shelters (bus shelter i is at node M + i)
// Node M+N+1: Sink (T)
int S = 0;
int marketStart = 1;
int busStart = marketStart + M; // Bus shelter nodes start at busStart.
int T = busStart + N;
int totalNodes = T + 1;
MinCostFlow mcf(totalNodes);
// Total number of people in all markets.
ll totalPeople = 0;
for (int i = 1; i <= M; i++){
totalPeople += P[i];
}
// 1. Add edges from source S to each market i.
for (int i = 1; i <= M; i++){
mcf.addEdge(S, i, P[i], 0);
}
// 2. For each market i, add three edges:
// - Edge to bus shelter i ("left" option): node busStart + (i-1)
// - Edge to bus shelter i+1 ("right" option): node busStart + i
// - Edge to sink T (buy umbrella): capacity U[i], cost 1
for (int i = 1; i <= M; i++){
mcf.addEdge(i, busStart + (i - 1), P[i], 0); // Left option.
mcf.addEdge(i, busStart + i, P[i], 0); // Right option.
mcf.addEdge(i, T, U[i], 1); // Umbrella option.
}
// 3. For each bus shelter i, add an edge from the bus shelter node to sink T with capacity B[i] and cost 0.
for (int i = 1; i <= N; i++){
mcf.addEdge(busStart + (i - 1), T, B[i], 0);
}
// Run the min-cost flow algorithm.
auto res = mcf.minCostFlow(S, T, totalPeople);
// Check if we could send all people from the markets.
if (res.first < totalPeople) {
cout << "NO\n";
return 0;
}
// Otherwise, print the result.
cout << "YES\n" << res.second << "\n";
// For each market i, extract flows on the three edges:
// index 0: Market i -> bus shelter i ("left")
// index 1: Market i -> bus shelter i+1 ("right")
// index 2: Market i -> sink T ("umbrella")
for (int i = 1; i <= M; i++){
assert(mcf.graph[i].size() >= 3);
ll left_flow = mcf.graph[i][0].orig - mcf.graph[i][0].cap;
ll right_flow = mcf.graph[i][1].orig - mcf.graph[i][1].cap;
ll umb_flow = mcf.graph[i][2].orig - mcf.graph[i][2].cap;
cout << left_flow << " " << umb_flow << " " << right_flow << "\n";
}
return 0;
}
