宝 物

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

题目描述


输入

输出

样例输入

6 7 5 1
1
2
3
4
5
1 2 3
3 6 2
6 2 10
2 4 1
5 1 1
4 5 1
1 6 1

样例输出

4

提示