Shopping Plans

You are shopping from a store that sells a total of $N$ items. The $i$-th item has a type $a_i$, which is an integer between $1$ and $M$. A feasible shopping plan is a subset of these items such that for every type $j$, the number of items of type $j$ is in the interval $[x_j, y_j]$.

The $i$-th item in the store has a cost of $c_i$, and the cost of a shopping plan is the sum of the costs of the items in the plan. Find the costs of the $K$ cheapest feasible shopping plans. If two different shopping plans have the same cost, they are counted separately in the output.

The first line contains three space-separated integers $N$, $M$, and $K$ ($1 \le N, M, K \le 200000$). The next $N$ lines each contain two space-separated integers $a_i$ and $c_i$ ($1 \le a_i \le M$, $1 \le c_i \le 10^9$). The next $M$ lines each contain two space-separated integers $x_j$ and $y_j$ ($0 \le x_j \le y_j \le N$).

Output $K$ lines. On the $i$-th line, output the cost of the $i$-th cheapest feasible shopping plan, or $-1$ if there are fewer than $i$ feasible shopping plans.

A feasible shopping plan must combine exactly one item with a cost in $\{5, 3, 6\}$ with exactly one item with a cost in $\{3, 1\}$.