Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Trong DotA, Morphling là một carry hạng nặng rất mạnh, nổi tiếng với kỹ năng Attribute Shift có khả năng chuyển đổi chỉ số giữa hai thuộc tính Agility và Strength, mang lại sự linh hoạt về cả kỹ năng và các cách build items cho hero này.

Sau hơn một thế kỷ, Morphling vẫn giữ được kỹ năng Attribute Shift đã làm nên tên tuổi của mình, dù nó đã được làm lại. Một hero của DotA bây giờ không chỉ có ba, mà là rất nhiều thuộc tính, do đó trước đây Attribute Shift cho phép Morphling 1 khả năng chuyển đổi qua lại giữa 2 thuộc tính, thì bây giờ Attribute Shift cung cấp n – 1 khả năng chuyển đổi qua lại xoay quanh n thuộc tính.

Cụ thể, khả năng thứ i (1 ≤ i ≤ n – 1) của Attribute Shift được mô tả bằng 2 số nguyên dương A_i và R_i, có nghĩa là Morphling có thể đổi R_i điểm của thuộc tính A_i thành 1 điểm thuộc tính i + 1, hoặc đổi từ 1 điểm thuộc tính i + 1 thành 1 điểm thuộc tính A_i. Các giá trị chuyển đổi luôn mang giá trị nguyên, có nghĩa là Morphling luôn đổi từ một giá trị nguyên của thuộc tính này thành giá trị nguyên của thuộc tính khác.

Ngoài ra kỹ năng ultimate của Morphling cũng được làm lại. Nó chỉ kích hoạt được khi thuộc tính thứ i của Morphling có không ít hơn Y_i điểm. Ban đầu thuộc tính thứ i của Morphling có X_i điểm. Hãy xác định xem Morphling có thể có cách chuyển đổi thuộc tính nào để có thể sử dụng được kỹ năng ultimate của mình hay không?

Input

Dòng đầu tiên gồm một số nguyên dương n (n ≤ 2.10⁵) là số lượng các thuôc tính khác nhau trong các khả năng chuyển đổi.

Dòng thứ hai gồm n số nguyên dương X_i (X_i ≤ 5.10¹¹) là các chỉ số ban đầu của thuộc tính.

Dòng thứ ba gồm n số nguyên dương Y_i (Y_i ≤ 5.10¹¹) là các chỉ số yêu cầu của các thuộc tính cho kỹ năng ultimate.

n – 1 dòng tiếp theo, dòng thứ i gồm 2 số nguyên dương A_i và R_i (1 ≤ A_i ≤ i, 1 ≤ R_i ≤ 5.10¹¹) là các thông số của khả năng chuyển đổi thứ i giữa 2 thuộc tính A_i và i + 1.

Output

Nếu có cách chuyển đổi giúp Morphling thực hiện kỹ năng ultimate của mình, in ra “YES”, ngược lại in ra “NO” (không có dấu ngoặc kép).

Example

Test 1:
Input:
4
3 1 6 2
1 2 4 2
1 1
2 3
3 1
Output:
YES

Test 2:
Input:
5
4 3 8 12 4
9 16 12 9 4
1 3
2 4
3 4
1 3
Output:
NO