题目描述
土豆大学拥有n座建筑物,编号从1到n,其中1号楼是学生宿舍,其他都是教学楼。所有建筑物之间均有m条双向路径相连,第i条路径连接xi和yi,长度为li,通过一条长度为li的路径需要li个单位时间。
小土豆是土豆大学的学生。她早上在宿舍起床,时间为0,开始学习。她的学习时间共有t个单位时间,从0时刻开始,到t时刻结束。在学习时间内,小土豆共有q节课程,第i节课在pi号楼上课,开始时间为ai,结束时间为bi。学完课程后,小土豆需要在t时刻回到宿舍。另外,在学习时间内,小土豆可以回宿舍睡觉。
小土豆懒惰但勤奋,因此她希望在至少睡眠s单位时间的情况下尽可能地上更多的课程。我们认为小土豆只有在ai到bi期间在pi号楼上课才算上了第i节课程。她一次只能上一门课,即使这两门课在同一栋建筑物里。请帮助小土豆找到在满足她的睡眠要求的情况下可以上的最多的课程数目。
输入格式
第一行包含五个整数n,m,q,t,s,表示建筑数量,道路数量,课程数量,总学习时间和所需睡眠时间。
接下来的 m 行中,每行包含三个整数 xi,yi,li,表示连接建筑 xi 和yi的双向路径的长度为 li。
接下来的 q 行中,每行包含三个整数ai,bi,pi,表示位于建筑 pi 的课程开始时间为 ai,结束时间为 bi。
输出格式
输出一行一个整数代表答案。
输入样例1
5 4 3 10 2
3 4 1
2 5 1
4 5 1
3 1 1
2 9 2
3 9 4
6 8 3
输出样例1
1
输入样例2
5 4 4 15 3
3 4 1
4 1 1
5 2 2
5 3 2
5 6 4
8 9 3
13 14 2
4 6 5
输出样例2
2
数据范围
对于30%的数据,保证n,m≤10。
对于60%的数据,保证n,m,t≤100。
对于所有数据,保证2≤n≤400, n−1≤m≤n(n−1)2, 1≤q≤400, 3≤t≤108, 0≤s≤t,1≤xi,yi≤n, 1≤li≤104,1≤ai<bi<t, 2≤pi≤n。