题目背景

由于数据包过大，本题无法上传全部数据。

题目描述

有 $N$ 个公交车站，标号为 $1, \ldots, N$。第 $i$ 个公交车站可以容纳 $B_{i}$ 个人。

对于每个 $i \in\{1, \ldots, N-1\}$，有一条人行道连接公交车站 $i$ 和公交车站 $i+1$，中间有一个露天市场。第 $i$ 个市场有 $U_{i}$ 把雨伞出售，每把雨伞的价格为 $\$ 1$。

现在，有 $P_{i}$ 个人在第 $i$ 个市场里面，所有的公交车站都是空的。

突然，天开始下雨，市场 $i$ 的每个人都必须在三种方案中选择一种：

• 去公交车站 $i$；
• 去公交车站 $i+1$；
• 留下来买一把雨伞。

如果一个人无法在某个公交车站下或者买一把雨伞，他们就会淋湿。

你需要回答如果在最优的安排方案下，能否确保每个人都能不被雨淋湿。如果是的话，你需要给出他们需要花费的最少的钱，以及每个人应该移动到哪个公交车站。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个用空格分隔的整数 $B_{i}\ (1 \leq i \leq N)$，表示公交车站 $i$ 的容量。

第三行包含 $N-1$ 个用空格分隔的整数 $P_{i}\ (1 \leq i \leq N-1)$，表示市场 $i$ 的人数。

第四行包含 $N-1$ 个用空格分隔的整数 $U_{i}\ (1 \leq i \leq N-1)$，表示市场 $i$ 出售的雨伞的数量。

输出格式

如果每个人都能在雨伞或公交车站下，输出 $N+1$ 行：

• 第一行输出一行 YES。
• 第二行输出一个整数，表示包含在雨伞上花费的最少的钱。
• 接下来的 $N-1$ 行，每行输出三个用空格分隔的整数分别表示市场 $i\ (1\leq i \leq N-1)$ 移动到公交车站 $i$ 的人数，市场 $i$ 买雨伞的人数，市场 $i$ 移动到公交车站 $i+1$ 的人数。

如果有多种合法方案，你可以输出任意一种。

否则，输出一行 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

提示

样例 1 解释

公交车站有 $35$ 个空位，没有雨伞出售，但市场有 $40$ 个人，所以答案是 NO。

样例 2 解释

市场 $1$ 中的 $10$ 个人会去公交车站 $1$，没有人会买雨伞，$10$ 个人会去公交车站 $2$。

市场 $2$ 中的 $5$ 个人会去公交车站 $2$，$5$ 个人会留下来买雨伞，$10$ 个人会移动到公交车站 $3$。

总共购买了 $5$ 把雨伞，花费了 $\$ 5$。

数据范围

对于所有的数据，有 $2 \leq N \leq 10^{6}$，$0 \leq B_{i} \leq 2 \cdot 10^{9}$，$0 \leq P_{i},U_{i} \leq 10^{9}$。

子任务编号	分值	$N$	$B$	$P$	$U$
$1$	$20$	$2 \leq N \leq 10^{6}$	$0 \leq B_{i} \leq 2 \cdot 10^{9} $	$0 \leq P_{i} \leq 10^{9}$	$U_{i}=0$
$2$		$2 \leq N \leq 2000$	$0 \leq B_{i} \leq 400$	$ 0 \leq P_{i} \leq 200$	$0 \leq U_{i} \leq 200$
$3$	$24$	$2 \leq N \leq 4000$	$0 \leq B_{i} \leq 4000$	$0 \leq P_{i} \leq 2000$	$0 \leq U_{i} \leq 2000$
$4$	$36$	$2 \leq N \leq 10^{6}$	$0 \leq B_{i} \leq 2 \cdot 10^{9}$	$0 \leq P_{i} \leq 10^{9}$	$0 \leq U_{i} \leq 10^{9}$