Description

There are $N$ items. Each item has a type $a_i$ and a price $c_i$.

For type $j$, you must buy a number of items within $[x_j, y_j]$, meaning you must buy at least $x_j$ items and at most $y_j$ items of this type.

You need to output the costs of the cheapest $K$ plans. If no such plan exists, output -1.

In particular, if two plans have the same total cost but are different in the specific set of chosen items, they are considered two different plans.

Input Format

The first line contains three integers $N, M, K$.

The next $N$ lines each contain two integers $a_i, c_i$.

The next $M$ lines each contain two integers $x_j, y_j$.

Output Format

Output $K$ lines. Each line contains one integer. The $i$-th line represents the cost of the $i$-th cheapest plan.

5 2 7
1 5
1 3
2 3
1 6
2 1
1 1
1 1

4
6
6
7
8
9
-1

Hint

Sample Explanation

There are $5$ items and $2$ types.

Type $1$: $\{3,5,6\}$, type $2$: $\{1,3\}$.

Both type $1$ and type $2$ can only choose one item.

For the cheapest plan, choose $\{1,3\}$.

And so on.

Subtasks

This problem uses bundled testdata.

• Subtask 1 ($20$ points): $x_j, y_j = 1$, $N, M, K \le 4\times 10^3$.
• Subtask 2 ($20$ points): $x_j, y_j = 1$, $N, M, c_i \le 4\times 10^3$.
• Subtask 3 ($20$ points): $x_j, y_j = 1$.
• Subtask 4 ($20$ points): $x_j = 0$.
• Subtask 5 ($20$ points): No special restrictions.

For $100\%$ of the testdata, it is guaranteed that $1\le N, M, K\le 2\times 10^5$, $1\le a_i\le M$, $1\le c_i\le 10^9$, $0\le x_j\le y_j\le N$.

Note

This problem is translated from Canadian Computing Olympiad 2020 Day 2 T3 Shopping Plans.

Translated by ChatGPT 5