题目描述

一家商店共有 $N$ 个物品。第 $i$ 个物品的类型为 $a_i$，价格为 $c_i$。类型编号均为 $1$ 到 $M$ 之间的整数。

一个购物方案是从这 $N$ 个物品中选出一个子集。对于每一种类型 $j$，方案中选出的类型 $j$ 物品数量必须在闭区间 $[x_j,y_j]$ 内。

购物方案的总价等于所选物品的价格之和。

请按总价从小到大输出前 $K$ 个合法购物方案的总价。如果两个不同的购物方案总价相同，它们仍然是两个方案，必须分别计数并重复输出该总价。

如果合法购物方案不足 $K$ 个，则在输出完所有合法方案后，用 $-1$ 补足到 $K$ 行。

输入格式

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

接下来 $N$ 行，第 $i$ 行包含两个整数 $a_i,c_i$，表示第 $i$ 个物品的类型和价格。

接下来 $M$ 行，第 $j$ 行包含两个整数 $x_j,y_j$，表示类型 $j$ 需要选择的物品数量范围。

输出格式

输出恰好 $K$ 行。

第 $i$ 行输出第 $i$ 便宜的合法购物方案总价；如果合法购物方案少于 $i$ 个，则输出 $-1$。

样例

样例输入 1

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

样例输出 1

4
6
6
7
8
9
-1

样例解释

第一类物品的价格为 $5,3,6$，第二类物品的价格为 $3,1$。合法方案必须在每一类中恰好选择一个物品。

所有合法方案的总价从小到大为

其中两个总价为 $6$ 的方案选择了不同的物品，因此都要计数。合法方案只有 $6$ 个，所以第 $7$ 行输出 $-1$。

数据范围

对于所有测试数据，满足：

• $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$；
• 所有输入均为整数。

注意：某个类型实际拥有的物品数可能少于 $x_j$，此时不存在合法购物方案。

子任务

限制

空间限制：512 MB。