Travel Merchant's Knapsack Challenge

Little S believes that every problem can be solved in polynomial time. Before setting off on his journey as a traveling merchant, he purchased some items. There are \(n\) kinds of these 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 can he load his knapsack to obtain the maximum profit?

Just before departure, Little S received a batch of special goods. There are \(m\) such goods. For the \(i\)th good, if an allocated volume \(X_i\) is used, its profit is given by the quadratic formula:

[ Y_i = a_iX_i^2 + b_iX_i + c_i ]

You are to help Little S maximize his total profit by selecting items from the first batch and deciding on a nonnegative integer volume \(X_i\) (possibly zero) for each of the \(m\) special goods such that the total used volume does not exceed \(C\). Note that for the ordinary items, each type \(i\) has \(D_i\) copies available, and for the special goods, you must decide an allocation for each good exactly once.

inputFormat

The first line contains three integers \(n\), \(m\), and \(C\).

The next \(n\) lines each contain three integers: \(V_i\), \(W_i\), and \(D_i\) for the ordinary items.

The next \(m\) lines each contain three integers: \(a_i\), \(b_i\), and \(c_i\) for the special goods.

outputFormat

Output a single integer representing the maximum total profit Little S can achieve.

sample

1 1 10
2 3 4
1 2 0

120