Có \(N\) ngôi nhà quanh hồ Beaver ở vương quốc JOI, được đánh số từ \(1\) đến \(N\) theo chiều ngược kim đồng hồ.

Mỗi ngôi nhà có thể dùng dịch vụ chuyển tiền để gửi tiền đến ngôi nhà liền kề bên trái khi nhìn từ hồ: nhà \(i\) gửi đến nhà \(i+1\) nếu \(1\le i<N\), còn nhà \(N\) gửi đến nhà \(1\). Phí chuyển tiền bằng đúng số tiền được gửi. Số tiền gửi phải là một số nguyên yên. Khi gửi tiền phải trả phí ngay, nên tổng số tiền gửi và phí không được vượt quá số tiền hiện có trong nhà.

Hiện tại, nhà \(i\) có \(A_i\) yên. Vì lý do thuế, người ta muốn nhà \(i\) có đúng \(B_i\) yên. Bạn chỉ được dùng dịch vụ chuyển tiền này; không được tiêu tiền vào việc gì khác ngoài phí chuyển tiền, cũng không được chuyển tiền bằng cách khác.

Hãy xác định liệu có thể làm cho số tiền của tất cả các ngôi nhà đồng thời bằng số tiền mong muốn hay không.

Dữ liệu vào

• Dòng đầu chứa \(N\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(A_i,B_i\).

Dữ liệu được đọc từ đầu vào chuẩn.

Dữ liệu ra

Ghi Yes nếu có thể đạt số tiền mong muốn ở mọi ngôi nhà bằng dịch vụ chuyển tiền; ngược lại, ghi No.

Ràng buộc

• \(2\le N\le 1\,000\,000\).
• \(0\le A_i\le 1\,000\,000\,000\) với \(1\le i\le N\).
• \(0\le B_i\le 1\,000\,000\,000\) với \(1\le i\le N\).

Phân nhóm

1. \(15\) điểm: \(N\le 7\), \(A_i\le 5\) và \(B_i\le 5\) với mọi \(1\le i\le N\).
2. \(40\) điểm: \(N\le 20\).
3. \(45\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

Nguồn

JOI Open Contest 2019, bài Remittance (remittance), ngày 14/7/2019. Bản dịch từ đề tiếng Anh chính thức của JCIOI, theo giấy phép CC BY-SA 4.0.