U633529 糖果（树形DP-C）

万圣节那天，小Q想去邻居要糖果，玩下“Trick or Treat”。 小Q家和邻居家够成一棵树，即邻居间可以相互到达，并且只有一种方案。 小Q的妈妈将在 $m$ 分钟后回来，如果发现小Q不在家会很生气。 小Q希望获得最多的糖果，并且在 $m$ 分钟内回到家中。 现在告诉你每条路要花的时间，并假设小Q到了邻居家后就能拿到糖果，不需要花时间，当然每个邻居只会给一次糖果，以后经过的时候，就不再给了。 请你帮她算算，她最多能拿到多少糖果。

输入数据一行，一个正数 $n$ 表示小Q所在的地方有多少户人家。 接下一行 $n$ 个数，表示每户人家给她的糖数 $val_i$。 接下来 $n-1$ ，每行三个数 $a$，$b$，$c$ ，表示通过连接编号为 $a$ ，$b$ 的人家的路要花费 $c$ 分钟的时间。 最后一行，两个整数 $k$，$m$ 。 $k$ 表示小Q家的编号（小Q也能从自己家获得糖果），$m$ 表示妈妈 $m$ 分钟后回家。

无

对于 30% 的数据 $1 \leq n \leq 10$ 对于 100% 的数据， $1 \leq n \leq 100$ ， $1 \leq m \leq 200$ ， $0 \leq val_i \leq 1000$ ， $1 \leq c \leq 10$ ； 样例一解释：小Q只能获得自己家的糖果，不能在 $m$ 分钟去其他的地方再赶回来。 样例二解释：小Q能获得自己家的糖果和编号为 $1$ 邻居家的糖果，并恰好在 $m$ 分钟赶回家中。