U529704 代肝传奇

小F是一位全能型游戏代肝。为了赚更多生活费,他要好好安排接下来的工作。

小F目前有 $n$ 个单子可以接，每个单子有一个开始日期 $a_i$ 和结束日期 $b_i$ 以及报酬 $v_i$。小F是一个专注的人，因此他不会在一天里同时进行 $w$ 项以上的代肝任务。小F有一个疲劳值，开始默认为 $0$，每工作一天就会累计疲劳值，一旦疲劳值大于 $k$ 小F就会直接暴毙。如果有一天小F没有任何工作，那么他的疲劳值会下降 $p$。小F不只接一种游戏的代肝，他会玩 $m$ 个游戏，他对每个游戏的喜爱度不同，因此代肝不同游戏时累积的疲劳值也会不同，他代肝游戏 $i$ 一天后增加的疲劳值为 $S_i$。现在请你安排他的工作计划，使他在不暴毙的情况下得到尽可能多的报酬。

第一行，输入 $m,n,w,k,p$。意思见题目描述。 第二行输入 $n$ 个整数，表示 $n$ 个代肝任务的目标游戏。 第三行输入 $m$ 个整数 $S_i$，意思见题目描述。 后 $n$ 行每行 $3$ 个整数 $a_i,b_i,v_i$。意思见题目描述。

输出仅一行，输出最大报酬。

对于 $20\%$ 的数据，$1 \leq n,m \leq 30$，$w=1$。 对于 $50\%$ 的数据，$1 \leq n,m \leq 10^3$，$w≤3$。 对于 $100\%$ 的数据，$1 \leq n,m \leq 10^6$，$w≤8$，$1 \leq k,p,a_i,b_i,v_i \leq 10^8$。