K Cheapest Purchase Strategies

You are given N items. Each item is characterized by its type a_i and a price c_i.

There are M distinct types. For the j^th type, you must select at least x_j and at most y_j items among those of that type. Note that even if two different selection methods yield the same total price, they are considered as distinct strategies.

Your task is to output the total prices of the first K cheapest distinct purchase strategies (in increasing order). If there are fewer than K strategies, output -1 instead.

The formulas used in the problem are in \(\LaTeX\) format. For example, the constraints for type \(j\) are \(x_j \leq \text{(number of items chosen)} \leq y_j\).

inputFormat

The first line contains three integers: N (number of items), M (number of distinct types), and K (number of strategies to output).

The next N lines each contain two integers: a_i and c_i, representing the type and price of the i^th item.

The following M lines each contain two integers: x_j and y_j (for \(j=1,2,\ldots,M\)), indicating that for type \(j\) you must choose at least \(x_j\) items and at most \(y_j\) items.

outputFormat

If there are at least K valid strategies, output the total costs of the first K cheapest strategies in increasing order, separated by spaces.

If fewer than K strategies exist, output -1.

sample

4 2 3
1 3
1 5
2 2
2 4
1 1
1 1

5 7 7