#3154. 「JOI Open 2019」汇款

内存限制:268 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

译自 JOI Open 2019 T2 「送金 / Remittance

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 元。你不能通过除给别的房子汇款和交手续费之外的方式花掉钱。

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

输入格式

第一行一个整数 N ,表示房子数目;

接下来 N 行,每行两个非负整数 A_i,B_i ,分别表示房子 i 的目前钱数和期望钱数。

输出格式

如果能让所有房子内钱数等于期望钱数,输出 Yes,否则输出 No

样例

样例输入 1

5
0 0
1 0
2 3
3 3
4 0

样例输出 1

Yes

样例说明 1

例如,按以下方法,可以让所有房子内钱数等于期望钱数。

  1. 从房子 5 给房子 1 2 元,并交手续费 2 元;
  2. 从房子 1 给房子 2 1 元,并交手续费 1 元;
  3. 从房子 2 给房子 3 1 元,并交手续费 1 元。

样例输入 2

5
0 0
1 2
2 4
3 2
4 0

样例输出 2

No

样例说明 2

通过汇款系统,你不可能使得所有房子的钱数等于期望钱数。

样例输入 3

2
1 1
2 1

样例输出 3

No

样例说明 3

注意汇款金额必须是整数。

样例输入 4

2
1 1
2 2

样例输出 4

Yes

样例说明 4

你不需要使用汇款系统。

数据范围与提示

对于全部数据, 1\le N\le 10^6,0\le A_i,B_i\le 10^9

详细子任务附加限制及分值如下:

  • 子任务 1 15 分): N\le 7,A_i,B_i\le 5
  • 子任务 2 40 分): N\le 20
  • 子任务 3 45 分):无附加限制。