题目描述

几天后你要去一家大商店购物，所以你提前制定购买计划。

商店里有 $N$ 件商品，第 $i$ 件商品的类型为 $t_i$，价格为 $c_i$。对于每一种类型 $j$，你都规定了购买数量的限制：类型 $j$ 的商品至少买 $l_j$ 件，至多买 $r_j$ 件。

一个购物计划的代价等于所购买商品价格之和。

请找出所有满足限制的购物计划中，代价最小的前 $K$ 个计划。若两种购物计划中存在某件商品被其中一个计划购买而另一个计划没有购买，则这两种计划视为不同。

输入格式

第一行包含三个正整数 $N,M,K$，分别表示商品数量、商品类型数量和需要输出的计划数量。

接下来 $N$ 行，每行两个整数 $t_i,c_i$，表示第 $i$ 件商品的类型和价格。

最后 $M$ 行，每行两个整数 $l_j,r_j$，表示类型 $j$ 商品购买数量的下界和上界。

输出格式

输出 $K$ 行。

第 $i$ 行输出满足所有限制的购物计划中第 $i$ 小的代价。

如果合法购物计划总数少于 $K$ 个，则对于不存在的名次输出 -1。

数据范围

• $1 \le N,M,K \le 200000$
• $1 \le t_i \le M$
• $1 \le c_i \le 10^9$
• $0 \le l_j \le r_j \le N$

子任务

只有通过某子任务及其所有依赖子任务的全部测试，才能获得该子任务分数。

样例

输入

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

输出

4
6
6
7
8
9
-1

说明

类型 $1$ 有三件商品，价格分别为 $5,3,6$；类型 $2$ 有两件商品，价格分别为 $3,1$。

最便宜的合法购物计划是购买第 $2$ 件和第 $5$ 件商品，总价为 $3+1=4$。

由于限制要求两种类型各买一件，因此总共有 $3\times 2=6$ 个合法计划，所以第 $7$ 个答案为 -1。