Bob 厌倦了玩游戏，离开了 Alice，独自前往长沙旅行。岳麓山、橘子洲、世界之窗、省博物馆等都是 Bob 想去的景点。然而，他的时间非常有限，无法全部游览。

假设长沙有 $N$ 个景点，Bob 为每个景点定义了一个满意度值 $S_i$。如果他游览了该景点，他的总满意度将增加 $S_i$。Bob 希望在有限的时间 $T$ 内，从景点 $S$ 出发，有选择地游览一些景点，最后在景点 $E$ 结束，使得总满意度尽可能大。显然，游览景点也需要花费一定的时间，假设游览景点 $i$ 需要花费 $C_i$ 个单位时间（$0 \le i < N$）。

请记住，Bob 可以选择路过某个景点而不游览它（包括 $S$ 和 $E$），也许他只是想走更短的距离以节省时间。

Bob 还有一个特殊要求，即他只会游览那些满意度严格大于他上一次游览的景点的景点。例如，如果他游览了一个满意度为 50 的景点，那么他接下来只会游览满意度为 51 或更高的景点。当然，景点之间的路径是双向的。

输入格式

第一行是一个整数 $W$，表示测试用例的数量，接下来是 $W$ 组数据。

每组测试数据的第一行包含五个整数：$N, M, T, S, E$。$N$ 表示景点数量，$1 < N < 100$；$M$ 表示路径数量，$0 < M < 1000$；$T$ 表示时间限制，$0 < T \le 300$；$S$ 表示 Bob 出发的景点；$E$ 表示结束的景点。（$0 \le S, E < N$）

测试数据的第二行包含 $N$ 个整数 $C_i$（$0 \le C_i \le T$），表示如果 Bob 游览景点 $i$ 所需的时间成本。

第三行包含 $N$ 个整数，表示游览景点 $i$ 可以获得的满意度 $S_i$（$0 \le S_i < 100$）。

接下来的 $M$ 行，每行包含三个整数 $u, v, L$，表示景点 $u$ 和 $v$ 之间有一条双向路径，从 $u$ 到 $v$ 或从 $v$ 到 $u$ 需要花费 $L$ 个单位时间。（$0 \le u, v < N, 0 \le L \le T$）

输出格式

第一行输出用例编号（格式参考样例输出）。 第二行包含一个整数，即最大满意度。 如果 Bob 无法在 $T$ 个单位时间内到达景点 $E$，则只需输出“0”（不含引号）。

样例

输入 1

1
4 4 22 0 3
1 1 1 1
5 7 9 12
0 1 10
1 3 10
0 2 10
2 3 10

输出 1

Case #1:
21