蚂蚁正在废弃的蚁丘中寻找食物。蚁丘有 $n$ 个房间和 $n-1$ 条连接它们的走廊。我们知道，任意两个房间之间都存在唯一的路径。换句话说，房间和走廊构成了一棵树。

每个房间都有一个入口，且只有一个走廊通向（或离开）它。在每个入口处，分别有 $g$ 组蚂蚁，数量分别为 $m_1, m_2, \dots, m_g$。这些蚁群将依次进入蚁丘，每一组在前一组完全进入后才会进入。在蚁丘内部，蚂蚁的探索方式如下：

• 当进入一个有 $d$ 条尚未被该蚁群探索过的走廊的房间时，蚁群会分裂成 $d$ 个等大的群体。每个新创建的群体会沿着其中一条走廊前进。如果 $d=0$，则该群体离开蚁丘。
• 如果蚂蚁无法平分，那么较强的蚂蚁会吃掉较弱的蚂蚁，直到可以进行完美平分。注意，这种平分总是可能的，因为蚂蚁数量最终会降至零。没有什么能阻止蚂蚁进行平分——特别是，蚂蚁可以吃掉自己，如果群体数量小于 $d$，最后剩下的一只蚂蚁也会这样做。

下图展示了 $m$ 只蚂蚁进入一个有三条待探索走廊的房间时，分裂成三个（等大）群体，每组 $\lfloor m/3 \rfloor$ 只蚂蚁的情况。

一只饥饿的食蚁兽挖开了其中一条走廊，现在可以吃掉所有经过该走廊的蚂蚁。然而，就像蚂蚁一样，食蚁兽对数字非常挑剔。它只会在经过的群体恰好由 $k$ 只蚂蚁组成时才将其吞食。我们想知道食蚁兽总共会吃掉多少只蚂蚁。

输入格式

第一行包含三个整数 $n, g, k$ ($2 \le n, g \le 1\,000\,000$, $1 \le k \le 10^9$)，用空格分隔。这些数字分别指定了房间数量、蚁群数量以及食蚁兽一次吞食的蚂蚁数量。房间编号从 $1$ 到 $n$。

第二行包含 $g$ 个整数 $m_1, m_2, \dots, m_g$ ($1 \le m_i \le 10^9$)，用空格分隔，其中 $m_i$ 表示第 $i$ 组蚂蚁在每个蚁丘入口处的数量。接下来的 $n-1$ 行描述了蚁丘内的走廊；第 $i$ 行包含两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n$)，用空格分隔，表示房间 $a_i$ 和 $b_i$ 之间由一条走廊连接。食蚁兽挖开了输入中出现的第一个走廊。

在总分 50% 的测试中，进入蚁丘的蚂蚁总组数不超过 $1\,000\,000$。此外，在占总分 20% 的子任务中，额外满足 $n, g \le 100$。

输出格式

程序应输出一行，包含一个整数：食蚁兽吃掉的蚂蚁总数。

样例

样例输入 1

7 5 3
3 4 1 9 11
1 2
1 4
4 3
4 5
4 6
6 7

样例输出 1

21

说明

在 2, 3, 5, 7 号房间旁，各有 5 组蚂蚁。食蚁兽会吃掉从 2 号房间开始探索的第一组中的 3 只蚂蚁，以及从 3, 5 或 7 号房间开始探索的第四组和第五组中各 3 只蚂蚁。

样例测试

• 1ocen: $n = 20, g = 20, k = 5$，房间以形成一条长隧道的方式连接。食蚁兽挖开了其中一端的走廊。蚁群大小为 $1, \dots, 20$。
• 2ocen: $n = 2^{19} + 1, g = 20, k = 1$，蚁丘结构如下：1 号房间与 $n$ 号房间相连（食蚁兽挖开了连接这两个房间的走廊），且第 $i$ 个房间（对于 $i = 2, 3, \dots, n-1$）与第 $\lfloor i/2 \rfloor$ 号房间相连。进入蚁丘的蚁群大小为 2 的连续幂次：$2^0, 2^1, \dots, 2^{19}$。