You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

译自 JOI Open 2019 T2 「送金」

JOI 王国的河狸湖边有 $N$ 座房子，按逆时针方向给房子从 $1$ 到 $N$ 编号。

站在湖所在的位置看，每一座房子可以给它左边相邻的房子汇款，即：对于房子 $i\ (1\le i\le N-1)$，它左边的房子是房子 $i+1$，对于房子 $N$，它左边的房子为房子 $1$。然而，汇一笔款的手续费等于汇款金额。汇款金额必须是一个整数。当你汇款的时候，你必须交手续费，所以汇款钱数和手续费之和不能超出房子里的钱数。

目前，房子 $i\ (1\le i\le N)$ 里有 $A_i$ 元。另一方面，从收税的角度来看，我们希望房子 $i$ 里的钱数等于 $B_i$。因此你希望利用汇款系统使得房间 $i$ 里钱数等于 $B_i$ 元。你不能通过除给别的房子汇款和交手续费之外的方式花掉钱。

给定每座房子目前有的钱数和期望钱数，写一个程序判断能否使得每间房子都达到期望的钱数。

输入格式

第 $1$ 行一个整数 $N$。

第 $2\sim N+1$ 行，每行两个整数 $A_i,B_i$，分别表示房子 $i$ 的目前钱数和期望钱数，用空格隔开。

输出格式

如果可以满足要求，输出 Yes，否则输出 No。

5
0 0
1 0
2 3
3 3
4 0

Yes

5
0 0
1 2
2 4
3 2
4 0

No

2
1 1
2 1

No

2
1 1
2 2

Yes

提示

数据范围：

$2\le N\le 10^6$，$0\le A_i\le 10^9$（$1\le i\le N$），$0\le B_i\le 10^9$（$1\le i\le N$）。

子任务：

1. （15 分）$N\le 7$，$A_i\le 5$，$B_i\le 5$（$1\le i\le N$）。
2. （40 分）$N\le 20$。
3. （45 分）没有额外约束。

样例解释：

举例来说，你可以按照以下支付方式，满足要求。

1. 房子 $5\to 1$，支付 $2$ 元。花费 $2$ 元。
2. 房子 $1\to 2$，支付 $1$ 元。花费 $1$ 元。
3. 房子 $2\to 3$，支付 $1$ 元。花费 $1$ 元。

你不能以任何方式满足要求。

注意钱必须以 $1$ 元作为单位支付。

你不需要使用支付系统。