小坑坑玩神庙逃亡

Time Limit: 1000MS

Memory Limit: 131072KB

Description

小坑坑觉得玩神庙逃亡太坑了,于是他破解了这个游戏。

众所周知神庙逃亡游戏是这样进行的:

玩家控制一名冒险者从起点开始不断的跑,其过程中不断收集金币和道具。而一旦玩家失误,冒险者就会被尾随其后的怪兽抓住,游戏就结束了。网络传言说神庙逃亡我们的冒险者一直跑下去终究会跑到终点,但是破解了这个游戏的小坑坑发现事实并非如此。

小坑坑对神庙逃亡的各种设定非常不满意,于是他对游戏的模式进行了一些修改:

小坑坑讨厌随机生成的地图,于是他每次用程序生成一张固定的地图,并为地图增加了终点。

由于冒险者一直受到怪物的追赶只能向前走,加之游戏跑重复的路线是非常无趣的,所以可以把地图看做是一张有N个点M条边的向无环图。(N <= 100, M <= 2000)

小坑坑在每个点上和每个边上都放置了一些宝箱,每个宝箱里有一定价值(Wi <= 1500)的宝物,冒险者在进过宝箱所在的点或边时可以选择是否拿走物品。当冒险者到达终点停下时,游戏会记录下这个冒险者所获得的宝物的总价值作为冒险者的分数;若不能到达终点,无论冒险者拿到多少宝物都不计分。

小坑坑觉得自己操作冒险者太坑了,于是他写了AI来进行游戏,久而久之他发现用一个冒险者进行游戏非常无聊,于是他准备让K(<= 15)个冒险者在同一张地图上同时进行游戏。

小坑坑想知道,他的所有冒险者一共最多能得多少分呢?

Input

题目有多组测试数据。

每组数据第一行有两个整数N,M

第二行有N个整数,Wi表示每个点上的宝箱宝物价值为Wi。

接下来有M行,每行有U,V,W三个整数表示(U,V)边上有宝箱权值为W。

最后一行有三个整数S、T、K,分别代表起点、终点编号和冒险者人数。

输入文件以EOF结尾。


Output

对于输入的每组数据,输出Case序数和小坑坑所能得到的最高分数。

Sample Input

4 5 
5 -2 7 9
1 2 9
1 3 5
1 4 -2
2 4 3
3 4 2
1 4 1

Sample Output

Case 1: 28

Hint

None

Source

None

提交代码