Description

Little S firmly believes that any problem can be solved in polynomial time, so he decides to be a traveling salesman for once. Before setting off, he bought some items. There are $n$ types of items; for the $i$-th type, the volume is $V_i$, the value is $W_i$, and there are $D_i$ items available. His knapsack has a capacity of $C$. How should he pack to obtain the maximum total value? As a top guru, he solved this easily.

However, just before departure, he received another batch of special goods. There are $m$ such goods, and for the $i$-th one, the relationship between its value $Y_i$ and the allocated volume $X_i$ is: $Y_i = a_i X_i^2 + b_i X_i + c_i$. This is good news, but Little S does not know how to handle it, so he turns to a super guru (that is, you) to help him solve this problem.

Input Format

The first line contains three integers $n, m, C$, as described above.
The next $n$ lines each contain three integers $V_i, W_i, D_i$, as described above.
The next $m$ lines each contain three integers $a_i, b_i, c_i$, as described above.

Output Format

Output a single line: the maximum value.

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

10

Hint

Sample explanation:
Take all of the first two types of items. Allocate volume $4$ to the last special good. The total value is $2 \times 3 + 4 \times 1 + (-1) \times 16 + 8 \times 4 + (-16) = 10$.

Constraints and Notes
For $100\%$ of the testdata, $1 \le n \le 10^4$, $1 \le m \le 5$, $1 \le C \le 10^4$, $1 \le W_i, V_i, D_i \le 1000$, $-1000 \le a_i, b_i, c_i \le 1000$.

Translated by ChatGPT 5