有 $N$ 个带顶棚的公交候车亭，编号为 $1, \dots, N$。第 $i$ 个候车亭可以容纳 $B_i$ 个人。
对于每个 $i \in \{1, \dots, N - 1\}$，候车亭 $i$ 和候车亭 $i + 1$ 之间有一条人行道，中间有一个露天市场。第 $i$ 个市场有 $U_i$ 把雨伞出售，每把售价 $1$ 美元。
目前，第 $i$ 个市场内有 $P_i$ 个人，且所有人都在市场中，因此所有候车亭都是空的。
突然下起了雨，市场 $i$ 中的每个人都必须在以下三种可能性中做出选择： 前往候车亭 $i$； 前往候车亭 $i + 1$；或者 * 留在原地并购买一把雨伞。
如果一个人无法在候车亭找到位置或买到雨伞，他们就会被雨淋湿。
如果每个人都能进行最优协调，他们是否都能保持干爽？如果可以，他们需要花费的最少金额是多少，以及每个人应该前往哪个候车亭？
输入格式
第一行包含 $N$。
第二行包含 $N$ 个空格分隔的整数 $B_i$ ($1 \le i \le N$)，表示候车亭 $i$ 的容量。
第三行包含 $N - 1$ 个空格分隔的整数 $P_i$ ($1 \le i \le N - 1$)，表示市场 $i$ 中的人数。
第四行包含 $N - 1$ 个空格分隔的整数 $U_i$ ($1 \le i \le N - 1$)，表示市场 $i$ 中出售的雨伞数量。
子任务
| 分数 | 候车亭数量 | 最大人数/候车亭 | 最大人数/市场 | 最大雨伞数/市场 |
|---|---|---|---|---|
| 5 分 | $2 \le N \le 10^6$ | $0 \le B_i \le 2 \cdot 10^9$ | $0 \le P_i \le 10^9$ | $U_i = 0$ |
| 5 分 | $2 \le N \le 2000$ | $0 \le B_i \le 400$ | $0 \le P_i \le 200$ | $0 \le U_i \le 200$ |
| 6 分 | $2 \le N \le 4000$ | $0 \le B_i \le 4000$ | $0 \le P_i \le 2000$ | $0 \le U_i \le 2000$ |
| 9 分 | $2 \le N \le 10^6$ | $0 \le B_i \le 2 \cdot 10^9$ | $0 \le P_i \le 10^9$ | $0 \le U_i \le 10^9$ |
输出格式
如果每个人都能通过雨伞或候车亭保持干爽，输出将包含 $N + 1$ 行：
第一行包含单词 YES。
第二行包含购买雨伞所需的最少金额。
接下来的 $N - 1$ 行，每行包含三个空格分隔的整数：
从市场 $i$ 前往候车亭 $i$ 的人数
在市场 $i$ 购买雨伞的人数
从市场 $i$ 前往候车亭 $i + 1$ 的人数
其中 $1 \le i \le N - 1$。
如果并非每个人都能保持干爽，输出一行包含单词 NO。
如果有多个可能的正确输出，接受任何一个正确的输出。
样例
样例输入 1
3 10 15 10 20 20 0 0
样例输出 1
NO
说明 1
候车亭共有 35 个位置，没有雨伞出售，但市场中有 40 个人。
样例输入 2
3 10 15 10 20 20 0 11
样例输出 2
YES 5 10 0 10 5 5 10
说明 2
观察市场 1，10 个人将前往候车亭 1，没有人购买雨伞，10 个人将前往候车亭 2。 观察市场 2，5 个人将前往候车亭 2，5 个人将留在原地购买雨伞，10 个人将前往候车亭 3。 总共购买了 5 把雨伞，花费 $5 美元。