XJY是一位勇敢的探险家，这一天他来到传说中的泥岗村岛寻找宝藏。

泥岗村有$n$个村庄和$n-1$条道路，且任意两个村庄可以相互到达。

第$i$个村庄里有价值为$V_i$的大秘宝（取走之后就没有啦）；对于第$i$条道路，XJY需要$T_i$天才能走完。现在XJY有$m$天的假期时间以供探险，他会从第$k$个村庄出发，最后回到第$k$个村庄。

问XJY最多能取走价值多少的宝藏？

输入格式

输入有多组数据（约50组）

第一行为一个整数$n$，表示共有$n$个村庄

第二行为$n$个整数$v_i$，表示宝藏价值

接下来$n-1$行表示$n-1$条道路，每行三个整数$u$ $v$ $t$，表示村庄$u$和$v$之间有道路相连，通行所需时间$t$

最后一行为两个整数$k$和$m$，意义如题所述

所有输入均为整数

输出格式

对于每组数据输出一行一个整数$ans$,表示获得宝藏的最大价值

样例

样例输入

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

样例输出

4
3
6

数据范围

• $1 \leq n \leq 100, 0 \leq Vi \leq 1000 , 1 \leq Ti \leq 10$
• $1 \leq k \leq n, 1 \leq m \leq 200$

数据范围与提示

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$65536\mathrm{KB}$