题目描述

译自 CCO 2020 Day2 T3「Shopping Plans」，翻译者：PinkRabbit。

你在一家商店内购物，总共有 $N$ 件商品。其中第 $i$ 件商品的类型是 $a_i$，它是一个在 $1 \sim M$ 之间的整数。

一个可行的购物计划（也就是选取这些商品的一个子集）必须满足：对于类型为 $j$ 的所有商品，被选中的个数必须在 $[x_j, y_j]$ 之间。

第 $i$ 件商品的价格为 $c_i$，而购物计划的代价就是所有选中的商品的价格之和。

请你求出最小的 $K$ 个可行的购物计划的代价。注意如果两个不同的购物计划有着相同的代价，你也应该要分别输出。

输入格式

第一行三个正整数 $N, M, K$。
接下来 $N$ 行，第 $i$ 行两个正整数 $a_i, c_i$。
接下来 $M$ 行，第 $j$ 行两个整数 $x_j, y_j$。

输出格式

输出 $K$ 行，第 $i$ 行输出第 $i$ 小的计划的代价，如果可行的计划数量不足 $i$ 个，则输出 $-1$。

样例

input

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

output

4
6
6
7
8
9
-1

一个可行的购物计划必须包含恰好一个价格属于 ${5, 3, 6}$ 的商品和恰好一个价格属于 ${3, 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$。