Kirole 有一颗 个果子的果树（即树形结构），每一条枝干可视为该果树的一条边，而枝干的交叉点或端点视为一个果子。
Kirole 为了实时记录果子的情况，需要在某些果子上部署监控。在第 个果子上部署监控的费用是 。当部署好后，与该果子直接相连的所有枝干均能被监控到。为了让 Kirole 花费最少，在保证整棵果树的所有枝干都被监控到的前提下，部署监控的花费要尽可能少。给定在每个果子部署监控的花费，请计算要使所有果子都能被监控到的最少花费是多少。
第一行一个正整数 表示果子的数量。
第二行 个正整数 表示在不同果子上部署监控的花费。
接下来 行，每行两个正整数 表示第 个果子与第 个果子之间有一条枝干。
输出一个整数，表示要使所有枝干均能被监控到的最少花费。
8 33 12 30 22 18 10 31 28 1 2 1 3 2 4 2 5 2 6 3 7 3 8
42
对于 的数据，保证