题目描述

李将军虽然没有叶书生那么荣华富贵，但确实是一位保家卫国的好将军。他曾经火速平定了渔阳的叛乱，你的历史书上说这至少使大唐的繁荣往后延续了三百年。

在渔阳山丘中，隐藏着 $n$ 个村落，通过若干条道路相连。目前你军队面前的是村落 $1$，你必须先攻占村落 $1$。

我们的摸金校尉重金买通了村落的平民，现在知道村落中有 $n-1$ 条单向道路相连，这些道路不存在环，所有的 $n$ 个村落都可以通过给出的道路到达。

李将军手下有充足的兵力。如果结点 $x$ 被攻占，与结点 $x$ 相连的且未被攻占的 $y$ 即可被攻占。

两军对垒，不需要厮杀。李将军只需要穿价格为 $jk_i \times lol_i$ 的女装即可迷倒据点 $i$ 中的所有敌军，兵不血刃地拿下村落。$jk_i$ 为据点 $i$ 具有的正整数常数，$lol_i$ 为据点 $i$ 被攻占的顺序，即据点 $i$ 是第 $lol_i$ 个被攻占的。

当然，穿已经穿过的女装敌军是不买账的，所以每到一个村落，他都需要重新购买女装。

李将军想知道他最少需要买多少钱的女装才能迷倒所有的敌军。

输入格式

输入仅一组数据。

对于每一组数据，第一行包含一个整数 $n$（$1 \leq n \leq 5000$），其中 $n$ 是村落的个数。

第二行包含 $n$ 个整数，其中第 $i$ 个是 $jk_i$（$1 \leq jk_i \leq 500$），是据点 $i$ 具有的正整数常数。

接下来的 $n-1$ 行中的每一行都包含两个间隔的村落编号 $v_1$ 和 $v_2$，它们是道路的两个端点，表示 $v_1$ 能到达 $v_2$。没有道路将被列出两次。

输出格式

对于每一组数据，输出仅一行，表示李将军最少需要花费的金钱。

样例输入

5
1 2 1 2 4
1 2
1 3
2 4
3 5

样例输出

33