Venus 有一个饥饿度 H ，食堂里共有 N 道菜，第 i 道菜需要 w_i 元，第 i 道菜有一个饱腹度F_i，同时有一个营养值 P_i . Venus 的嘴很刁，对于相同的菜， Venus 最多只会吃一次.

众所周知，有一些菜一起吃是会得到额外的营养（也有可能中毒）的，我们已知  M个组合，如果同时点了某个组合中的两道菜 A_i 和 B_i 则会额外提供一个 v_i 的营养值

Venus 想要在吃饱的同时，获得更多的营养，但是Venus 只有 W 元钱了，由于他实在是太饿了，所以希望你来帮他计算一下如何点菜才可以吃饱的情况下获得最高的营养值，如果怎么都吃不饱，请输出QAQ.

Tips: 由于 Venus 实在是太苣了，我们均认为他能吃的下所有点来的菜。另外，因为Venus实在是太太太太饿了，所以他最多只能等待1s

第一行，4 个正整数 N,M,H,W 

接下来 N行，每行 3 个整数，分别表示w_i,F_i,P_i

接下来 M行，每行 3 个整数，分别表示A_i,B_i,v_i

一行一个整数，表示 Venus 在保证能够吃饱的状态下可以获得的最大营养值

对于10%的数据，1 <= N <= 3;0 <= W <= 30

对于30%的数据，1 <= N <= 10;0 <= W <= 100  

对于100%的数据，

1 <= N <= 100;0<= M<= n/2;0 <= H <= 1000;0 <= W <= 500

0 <= w_i<= 1000;-500 <= F[i],P[i],v[i] <= 500

所给出的组合必定合法且没有重复，所有F[i]之和不超过5000