Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Chemistry in Berland

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIgor is a post-graduate student of chemistry faculty in Berland State University (BerSU). He needs to conduct a complicated experiment to write his thesis, but laboratory of BerSU doesn't contain all the materials required for this experiment.

Fortunately, chemical laws allow material transformations (yes, chemistry in Berland differs from ours). But the rules of transformation are a bit strange.

Berland chemists are aware of *n* materials, numbered in the order they were discovered. Each material can be transformed into some other material (or vice versa). Formally, for each *i* (2 ≤ *i* ≤ *n*) there exist two numbers *x*_{i} and *k*_{i} that denote a possible transformation: *k*_{i} kilograms of material *x*_{i} can be transformed into 1 kilogram of material *i*, and 1 kilogram of material *i* can be transformed into 1 kilogram of material *x*_{i}. Chemical processing equipment in BerSU allows only such transformation that the amount of resulting material is always an integer number of kilograms.

For each *i* (1 ≤ *i* ≤ *n*) Igor knows that the experiment requires *a*_{i} kilograms of material *i*, and the laboratory contains *b*_{i} kilograms of this material. Is it possible to conduct an experiment after transforming some materials (or none)?

Input

The first line contains one integer number *n* (1 ≤ *n* ≤ 10^{5}) — the number of materials discovered by Berland chemists.

The second line contains *n* integer numbers *b*_{1}, *b*_{2}... *b*_{n} (1 ≤ *b*_{i} ≤ 10^{12}) — supplies of BerSU laboratory.

The third line contains *n* integer numbers *a*_{1}, *a*_{2}... *a*_{n} (1 ≤ *a*_{i} ≤ 10^{12}) — the amounts required for the experiment.

Then *n* - 1 lines follow. *j*-th of them contains two numbers *x*_{j + 1} and *k*_{j + 1} that denote transformation of (*j* + 1)-th material (1 ≤ *x*_{j + 1} ≤ *j*, 1 ≤ *k*_{j + 1} ≤ 10^{9}).

Output

Print YES if it is possible to conduct an experiment. Otherwise print NO.

Examples

Input

3

1 2 3

3 2 1

1 1

1 1

Output

YES

Input

3

3 2 1

1 2 3

1 1

1 2

Output

NO

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/17/2019 22:25:14 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|