P6646 [CCO 2020] Shopping Plans

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.

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 $K$ lines. Each line contains one integer. The $i$-th line represents the cost of the $i$-th cheapest plan.

#### 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](https://cemc.math.uwaterloo.ca/contests/computing/2020/) [Day 2](https://cemc.math.uwaterloo.ca/contests/computing/2020/cco/day2.pdf) T3 Shopping Plans. Translated by ChatGPT 5