UOJ Logo Sharp Sword 剑锋 OI

SSOI

#22. 开心农场

统计

【问题描述】

    这个夏天,与众不同。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】

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】

1 1 24 2
10 6 5
0 6

【输出样例2】

0
(种第一种作物还亏钱,不如不种)

【时空限制】

1S
512MB
对于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。