【问题描述】

有时候，OIER喜欢在自己的房间里放些“相当流行”的歌曲，因为这样能让他心情舒畅（别人就不知道了。。）当然，OIER对歌曲也是有选择的，有的歌他只听一遍就不想听了，有的歌他听几遍就厌烦了，还有的歌他百听不厌，所以选择的歌不同OIER的快乐度也不同。

OIER很忙，他只有一段时间能拿来听歌，但是他又想自己的快乐度更高。。所以他请你帮忙，看他最多能收获多大的快乐度。

（注意：因为是OIER自己选的歌，所以都是增加他的快乐度，而不是降低）

【输入格式】：

第一行为四个整数T,n1,n2,n3，表示OIER最多可听T分钟的歌；他一共可以选择n1+n2+n3首歌，其中n1首他只想听一遍，n2首他想听几遍，n3首他百听不厌。

接下来n1行，每行两个整数x，y ，表示此首歌要播放x分钟，听完此歌OIER可收获y的快乐度。

接下来n2行，每行三个整数x，y，z，x，y意义同上，z表示OIER最多会听z遍此歌。

接下来n3行，每行两个整数x，y，意义同上。

【输出格式】：

一个整数，表示OIER能收获的最大快乐度。

【样例输入】：

10 3 2 1
10 1
8 5
3 5
1 2 3
1 5 1
5 5

【样例输出】：

17

（选择播放第三首歌一次，第四首一次，第五首一次，第六首一次，共用时10分钟）

【数据规模】：

x≤T≤1000；n1+n2+n3≤1000；z≤5；y≤10000； 保证结果在longint内。