Migrated from Lutece 2440 君の名前は？唱：“达拉崩吧斑得贝迪卜多比鲁翁” Ⅱ

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

此题是 G 题的困难版本，和 G 题唯一的不同是数据范围和时间范围。

勇者达拉崩吧斑得贝迪卜多比鲁翁战胜了恶龙！恶龙的山洞里有非常多的宝藏，其中有 $n$ 种普通物品，第 $i$ 种体积为 $V_i$ ，价值为 $W_i$ ，共有 $D_i$ 件。还有 $m$ 件神奇物品，第 $i$ 件的价值 $W_i$ 与分配的体积 $V_i$ （非负整数）之间的关系为：

达拉崩吧斑得贝迪卜多比鲁翁有一个体积为 $C$ 的背包，达拉崩吧斑得贝迪卜多比鲁翁想知道他用背包装宝藏的最大收益是多少，他决定向聪明的你请教这个问题。

Input

第一行三个数 $n(1 \le n \le 10^4)$，$m (1\le m \le 5)$，$C(1\le C\le 10^4)$，如题中所述；

以下 $n$ 行，每行有三个数 $V_i,W_i, D_i(1\le V_i,W_i, D_i \le 1000)$ 如题中所述；

以下 $m$ 行，每行有三个数 $x_i, y_i, z_i(-1000\le x_i, y_i, z_i \le 1000)$ 如题中所述。

Output

输出一个整数，表示最大收益。

Samples

2 1 10
1 2 3
3 4 1
-1 8 -16

10

Resources

2020 UESTC ICPC Training for Dynamic Programming