WYZ的跑步计划

题目背景

zzq 蒟蒻为了逃避学习所以在机房颓废学习OI，可是不久他就发现学习 oi 太无聊啦！！所以他开始颓废了起来。。。

可是 wyz 嫌 zzq 的身体太差了！所以让他每天都去跑步！

这下 zzq 可为难了，他要学习，要颓废，哪有时间跑步呢？

题目描述

在 zzq 的一天中有 $m$ 个小时，有着 $n$ 道题准备做，有 $k$ 个游戏可以玩，同时还要再 wyz 的压迫下在 $a$ 到 $b$ 这段时间内去跑步（我太难了

对于每一道题 $i$ 都需要占用 zzq $x_i$ 的时间去完成，同时可以给 zzq $y_i$ 的提高度，也会消耗 $z_i$ 的愉悦度；

当做这道题时（之前）的愉悦度小于 $0$ 时，这道题所获得的提高度会变成 $\lfloor\frac{y_i}{2}\rfloor$

而对于每一个游戏 $i$，都需要占用 zzq $u_i$ 的时间，同时给予 zzq $w_i$ 的愉悦度；

因为 zzq 不喜欢跑步，所以对于跑步来说，有一个愉悦度指标 $q$ 表示跑步会消耗 $q$的愉悦度 ；

zzq 一天开始的时候的愉悦度是一个给定的数 $p$

csp 马上就要来了，请你帮他计算一下这一天他最多能够获得多少提高度吧！

输入格式

输入文件的第一行包含 $7$ 个整数，依次为 $m,n,k,p,a,b,q$；

接下来 $n$ 行，依次表示每一道题。每行包括三个数 $x_i,y_i,z_i$；

接下来 $k$ 行，依次表示每一款游戏。每行包括两个数 $u_i,w_i$；

输出格式

输出一行一个整数，表示 zzq 这一天所能获得的最大提高度；

输入输出样例

还没有

提示及数据说明

由于zzq很弱，所以又可能有某些题一天都做不完

由于zzq喜欢oi，所以有可能做题降低的愉悦度可能是负的，也就是提升愉悦度

由于zzq颓废的时候有时候会有罪恶感，所以有些游戏获得的愉悦度可能是负的，也就是降低愉悦度

数据范围：对于100%的数据保证：

$$\sum{y_i}<2^{31}-1$$
$$-100<\sum{w_i}<100$$
$$0 \le n,k\le10$$
$$0\le m\le 1000$$
$$0\le a\le b\le m$$

数据保证无论如何愉悦度都在 $-100$ 到 $100$ 之间

（显然易见的dp）