描述

这个夏天，与众不同。QQ空间也引入了最近流行的社区交互类游戏《开心农场》。自然而然地，Chroi也成为了众多农场主的一员。可是Chroi整个暑假忙于OI，没什么时间照顾农场，这就需要你的帮助了。他可以告诉你他每天那些时间可以上线，你要做的就是告诉他该天最多可赚多少钱（为了降低难度，假设腾讯每天晚上0:00清空还没收获的作物，而且由于Chroi的农场等级比较低，所以只能种单季作物（就是只能收获一次的））。

在开心农场中，每个用户都有一定数目的土地，每次上线可以做的事是在土地上摘果实、卖果实、种下种子，每块土地上只能种一种作物，每块土地各自独立。

假设Chroi每次只能上线1秒，他能在瞬间做完所有他想做的事，所以你的程序要在一秒内得出结果。而且如果Chroi在一天的最后时刻上线，那他此刻做的事算第二天的。（比如时间为24，那他在24时刻做的事算第二天的0时刻做的。）

格式

输入格式

输入文件包含多行，第一行有三个正整数n,m,t,k，分别表示Chroi的农场中有n块地，共有m种作物可以选择，一天的时间t，有k个时刻Chroi可以上线。
接下来的m行每行输入三个正整数，第一个数字表示种子价格，第二个数字表示种子成熟时间（小于t），第三个数字表示成熟后果实的售价。再次提示，这些都是整数。
再接下来的一行有k个自然数，保证该整数为0,1,2...t-1中的一个，为Chroi可以上线的时间。这k个自然数不会重复。
输入文件到此结束。

输出格式

输出文件只有一个整数，表示Chroi每天可以获得的最大金钱数。

样例1

样例输入1

6 3 24 4
10 6 20
15 3 18
11 3 19
0 6 12 18

样例输出1

180
（共种了3次第一种作物，每次种6块土地，收获了3次，每次收获6块土地，最后一次上线18的时候只收获，不种植（之后不能再收获，再种植没时间收获，只能亏钱））

样例2

样例输入2

1 1 24 2
10 6 5
0 6

样例输出2

0
（种第一种作物还亏钱，不如不种）

限制

各个测试点1s

提示

【数据范围】
对于30%的数据，0<n<=10,0<m<=50,0<k<=t<=50。

对于50%的数据，0<n<=20,0<m<=500,0<k<=t<=500。

对于100%的数据，0<n<=50,0<m<=3000,0<k<=t<=3000，最后输出的数<maxlongint。

来源

HOI 2009