### 问题描述

在一个古老的王国中，有 $n$ 个城市，这些城市由 $n-1$ 条路相互连接，形成了一个旅游图。旅游图中，每个城市都有一个代表该城市过路费的数字 $w_i$。

现在，一位名叫“小智”的旅游家计划进行 $k$ 次旅游之旅，每次旅游他需要从起点 $u$ 出发，经过到目的地 $v$ 的所有城市。在每个城市，小智需要交纳相应的过路费 $w_i$。现在，请你帮助小智计算 $k$ 次旅游之后的总花费。

输入格式

第一行输入两个正整数 $n$ 和 $k$，其中 $n$ 表示城市的数量，$k$ 表示旅游次数，$1 \le n \le 10^4$，$1 \le k \le 100$。

第二行输入 $n$ 个正整数 $w_i$，其中 $w_i$ 表示第 $i$ 个城市的过路费，$1 \le w_i \le 1000$。

接下来 $n-1$ 行，每行输入两个整数 $u_i$ 和 $v_i$，表示城市 $u_i$ 和城市 $v_i$ 之间有一条双向路，$1 \le u_i,v_i \le n$。

接下来 $k$ 行，每行输入两个整数 $x_i$ 和 $y_i$，表示第 $i$ 次旅游是从城市 $x_i$ 到城市 $y_i$，$1 \le x_i,y_i \le n$。

输出格式

输出仅一行，一个整数，表示小智进行 $k$ 次旅游之后的总花费。

样例输入

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

样例输出

25