题目描述

小D将要参加露营啦, 可是他并没有合适大的背包, 这个背包最多装载体积为 $V$ 的东西 ，他想起来家里有 $n$ 块布料, 这 $n$ 块布料可以经过小D的加工后可以使背包扩大的容积, 第 $i$ 块可以扩大 $p_i$ 的容积, 但小D也是人, 他在扩充背包的同时, 对于第 $i$ 块布料, 需要消耗 $q_i$ 的精力.

扩展完背包后, 接下来是装露营所需要的东西了. 一共有 $m$ 个露营用品, 对于第 $i$ 个用品, 它的体积为 $v_i$, 重要度为 $w_i$. 当然, 每个用品都有它独特的重量, 所以小D在把他们放进背包中同样需要 $q_i$ 的精力. 小D也是人! 他有一个精力值上限, 为$L$, 如果他太累了, 就不能去露营了.

现在小D求助你, 他想知道他在精力不被耗光, 背包不会溢出的情况下最大重要度是多少?

输入格式

第一行四个整数, 分别为 $n\ m\ L\ V$

第二到第 $n+1$ 行, 每行有两个整数, 分别为 $p_i$ 和 $q_i$

接下来 $m$ 行, 每行有三个整数, 分别为 $v_i\ w_i\ q_i$

输出格式

一个整数, 表示小D在精力不被耗光, 背包不会溢出的情况下的最大重要度.

样例输入

3 5 7 10
10 2
5 1
1 1
10 10 5
1 1 1
23 2 4
9 5 2
1 20 1

样例输出

36

提示

$1≤n,m,L≤100$

$1\le V \le 10$

$1\le p_i, q_i, v_i, w_i\le 100$