← 返回题目列表

Codeforces · 1373/F

F. 网络覆盖

中文机器翻译题面 查看原题

Berland 政府决定改善其国家的网络覆盖范围。贝尔兰有一个独特的结构:首都位于中心,而$$$n$$$城市环绕在首都周围。首都已经拥有良好的网络覆盖(因此政府忽略它),但第 $$$i$$$ 个城市包含需要连接的 $$$a_i$$$ 个家庭。

政府制定了一项计划,在所有相邻城市之间建立 $$$n$$$ 网络站,仅维持这些城市的连接。换言之,第$$$i$$$网络站将只为第$$$i$$$及第$$$(i + 1)$$$城市提供服务(第$$$n$$$站连接至第$$$n$$$及第$$$1$$$城市)。

所有网络站点都有容量:第$$$i$$$个站点最多可为$$$b_i$$$个家庭提供连接。

现在政府要求你检查设计的站点是否能够满足所有城市的需求——即是否可以为每个家庭分配一个网络站点,使得每个网络站点$$$i$$$最多提供$$$b_i$$$家庭的连接。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含单个整数 $$$n$$$ ($$$2 \le n \le 10^6$$$) — 城市和车站的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 ($$$1 \le a_i \le 10^9$$$) — 第 $$$i$$$ 个城市的家庭数量。

每个测试用例的第三行包含 $$$n$$$ 整数 ($$$1 \le b_i \le 10^9$$$) — 设计站点的容量。

保证测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,如果设计的站点能够满足所有城市的需求,则打印 YES,否则打印 NO(不区分大小写)。

示例

输入 #1

5
3
2 3 4
3 3 3
3
3 3 3
2 3 4
4
2 3 4 5
3 7 2 2
4
4 5 2 3
2 3 2 7
2
1 1
10 10

输出 #1

YES
YES
NO
YES
YES

注意

在第一个测试用例中:

- 第一个网络站可以提供到第一个城市的$$$2$$$连接和到第二个城市的$$$1$$$连接;
- 第二个车站可以提供$$$2$$$连接到第二个城市和$$$1$$$连接到第三个城市;
- 第三站可以提供 $$$3$$$ 到第三个城市的连接。

在第二个测试用例中:

- $$$1$$$-st 车站可以提供 $$$2$$$ 到 $$$1$$$-st 城市的连接;
- 第 $$$2$$$-nd 站可以提供 $$$3$$$ 到 $$$2$$$-nd 城市的连接;
- $$$3$$$-rd 站可以提供 $$$3$$$ 到 $$$3$$$-rd 城市的连接以及 $$$1$$$ 到 $$$1$$$-st 站的连接。

在第三个测试用例中,第四个城市需要 $$$5$$$ 个连接,但第三个和第四个站点总共有 $$$4$$$ 个连接。