无惨规避计划

内存限制: 128M   时间限制: 1S

题目描述


输入

输出

样例输入

4 4 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3

样例输出

10