题目描述
给定一棵 个结点的树，结点编号为 到 ，其中 号结点是树根。每个结点 有一个花费 和一个权值 。
你需要选出一些结点组成集合 ，满足：
- ，即根结点必须被选中；
- 在树上是连通的，即 中任意两个结点之间简单路径上的所有结点都属于 ；
- 。
请求出 的最大值。
输入格式
第一行两个整数 。
第二行 个整数 ，表示每个结点的花费。
第三行 个整数 ，表示每个结点的权值。
接下来 行，每行两个整数 ，表示结点 与结点 之间有一条边。
数据保证给出的边构成一棵树，且 ，因此至少可以只选根结点。
输出格式
输出一行一个整数，表示满足条件的集合的最大权值和。
样例
样例 1
输入：
4 5
2 1 1 2
10 3 4 5
1 2
1 3
3 4
输出：
19
解释：选择 ，它在树上连通（路径 上的点全在 中），花费 ，权值和为 。若选全部四个结点，花费为 不可行；因此答案为 。
样例 2
输入：
2 1
1 1
5 9
1 2
输出：
5
解释：，选中根结点就已用光花费，不能同时选 号结点，最大权值和为 。
数据范围
- ；
- ；
- ；
- ；
- 保证 ；答案不超过 ，可用 64 位整数存放。