题目描述

有 $N$ 个商品，每个商品有个种类 $a_i$，有个价格 $c_i$。

对于第 $j$ 个种类，必须购买个数位于 $[x_j,y_j]$ 的商品，即最少购买 $x_j$ 个，最多购买 $y_j$ 个该种类的商品。

您需要求出前 $K$ 种便宜的方案所需的价钱，如果没有这样的方案，请输出 -1。

特别的，如果有相同钱数，但是具体方案不相同的，算作两种方案。

输入格式

第一行为三个整数 $N,M,K$。

接下来 $N$ 行，一行两个整数 $a_i,c_i$。

接下来 $M$ 行，一行两个整数 $x_j,y_j$。

输出格式

共 $K$ 行，一行一个整数，第 $i$ 行表示第 $i$ 便宜的方案所需的价钱。

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

4
6
6
7
8
9
-1

提示

样例解释

共有 $5$ 个商品，$2$ 种类型。

类型 $1$：$\{3,5,6\}$，类型 $2$：$\{1,3\}$。

类型 $1$ 与类型 $2$ 均只能选择一个商品。

对于最便宜的方案，选择 $\{1,3\}$ 即可。

以此类推。

子任务

本题使用捆绑测试

• Subtask 1（$20$ 分）：$x_j,y_j=1$，$N,M,K\le4\times 10^3$。
• Subtask 2（$20$ 分）：$x_j,y_j=1$，$N,M,c_i\le 4\times 10^3$。
• Subtask 3（$20$ 分）：$x_j,y_j=1$。
• Subtask 4（$20$ 分）：$x_j=0$。
• Subtask 5（$20$ 分）：无特殊限制。

对于 $100\%$ 的数据，保证 $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$。

说明

本题译自 Canadian Computing Olympiad 2020 Day 2 T3 Shopping Plans。

本题数据有所删减。