← 返回题目列表

Codeforces · 846/E

E. 伯兰的化学

中文机器翻译题面 查看原题

Igor 是伯兰州立大学 (BerSU) 化学系的研究生。他需要进行一项复杂的实验来完成他的论文,但BerSU的实验室并没有这个实验所需的所有材料。

幸运的是,化学定律允许物质转变(是的,伯兰的化学与我们的不同)。但变换的规则有点奇怪。

Berland 化学家知道 n 种材料,按照它们发现的顺序编号。每种材料都可以转化为其他材料(反之亦然)。形式上,对于每个 i (2 ≤ i ≤ n),存在两个数字 xi 和 ki 表示可能的转换:ki 千克材料 xi 可以转换为 1 千克材料 i,1 千克材料 i 可以转换为 1 千克材料 xi。 BerSU 的化学处理设备只允许进行这样的转换,即所得材料的数量始终为整数千克。

对于每个 i (1 ≤ i ≤ n),Igor 知道实验需要 ai 公斤材料 i,而实验室包含 bi 公斤这种材料。是否可以在转化一些材料(或不转化)后进行实验?

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — Berland 化学家发现的材料数量。

第二行包含 n 个整数 b1, b2... bn (1 ≤ bi ≤ 1012) — BerSU 实验室的用品。

第三行包含 n 个整数 a1, a2... an (1 ≤ ai ≤ 1012) — 实验所需的数量。

接下来是 n - 1 行。其中第 j 个包含两个数字 xj + 1 和 kj + 1,表示第 (j + 1) 个材料的变换(1 ≤ xj + 1 ≤ j,1 ≤ kj + 1 ≤ 109)。

输出

如果可以进行实验,请打印“是”。否则打印NO。

示例

输入 #1

3
1 2 3
3 2 1
1 1
1 1

输出 #1

YES

输入 #2

3
3 2 1
1 2 3
1 1
1 2

输出 #2

NO