AzoresCabbage的苏州游

Time Limit: 1000ms

Memory Limit: 65535KB

Description

    AzoresCabbage假期的时候独自去苏州玩,出发前他想制定一个旅行计划。假设苏州有N个景点,AzoresCabbage给每个景点定义了一个开心值Si,也就是说当他游玩这个景点后他的总开心值会加Si,同时,游玩第i个景点会花费Ci的时间。由于没有妹子陪,所以他想在限定的时间T内,从起始点S,有选择的游览一些景点,最后到达终点E。当然他想让这次旅行所得的开心值最大。
    注意,AzoresCabbage可以为了走近路而只是路过一些景点,不去游玩(包括S和E)。而且他有一个怪癖就是要去玩的下一个景点的开心值一定要大于之前玩的景点(例如他游玩景点i获得的开心值为10,那么他游玩的下一个景点的开心值必须大于10)。此外,景点间的路是双向的,路上也要耗费时间。

Input

有多组测试数据。每组测试数据格式如下:
第一行包括5个整数:N M T S E。N代表景点的数量1<N<100,M代表道路的数量0<M<1000,T代表时间限制0<T<=300,S代表起点,E代表终点,0<=S,E<N。
第二行包括N个整数Ci(0<=Ci<=T),表示游玩景点i所要花费的时间。
第三行包括N个整数Si(0<=Si<100),表示游玩景点i可以得到的开心值。
接下来M行,每行包括3个整数u,v,w,表示在u和v间有一条双向路,在路上要耗费w的时间(0<=u,v<N,0<=w<=T)。

Output

第一行输出case号(格式见样例)
第二行包括一个整数,表示这次旅行可以获得的最大开心值。当然,如果不能再T时间内到达E,只需要输出“0”(没有引号)。

Sample Input

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

Sample Output

Case #1:
21

Hint

None

Source

None

提交代码