lntanx delivers urea fertilizer to farms. A farm has placed an order that requires containers of ammonia to make the fertilizer. The warehouse has no ammonia left, so lntanx decides to purchase nitrogen and hydrogen and synthesize the ammonia.
One synthesis batch consumes container of nitrogen and containers of hydrogen and produces containers of ammonia. Synthesis has no additional cost. Only whole batches can be made, and producing more ammonia than needed is allowed.
There are nitrogen suppliers and hydrogen suppliers. Each supplier has a stock quantity and a price per container. You may buy any whole number of containers up to a supplier's stock and split your purchases of a material among multiple suppliers.
Find the minimum cost of purchasing enough raw material to obtain at least containers of ammonia.
The first line contains three space-separated integers , , and , the counts of nitrogen and hydrogen suppliers and the required amount of ammonia.
The next lines describe the nitrogen suppliers, one per line. The following lines describe the hydrogen suppliers, one per line. Each supplier's line contains two space-separated integers and , its stock quantity and its price per container.
Print the minimum cost on the first line. If the available raw materials cannot produce at least containers of ammonia, print -1.
A signed 64-bit integer type is recommended for computing the cost.
Buying containers of nitrogen from the first supplier and unit from the second costs . Buying containers of hydrogen from the first supplier and containers from the second costs . These materials produce containers of ammonia.