你正在一家商店购物，该商店共出售 $N$ 件物品。第 $i$ 件物品的种类为 $a_i$，它是一个介于 $1$ 和 $M$ 之间的整数。一个可行的购物计划是这些物品的一个子集，满足对于所有种类 $j$，种类 $j$ 的物品数量在区间 $[x_j, y_j]$ 内。

商店中第 $i$ 件物品的花费为 $c_i$，一个购物计划的花费是该计划中所有物品的花费之和。你对可行购物计划的可能花费很感兴趣。请找出花费最小的 $K$ 个可行购物计划的花费。注意，如果有两个不同的购物计划花费相同，它们在输出中应被分别计算。

输入格式

第一行包含三个空格分隔的整数 $N$、$M$ 和 $K$（$1 \le N, M, K \le 200\,000$）。

接下来 $N$ 行，第 $i$ 行包含两个空格分隔的整数 $a_i$ 和 $c_i$（$1 \le a_i \le M$，$1 \le c_i \le 10^9$）。

接下来 $M$ 行，第 $j$ 行包含两个空格分隔的整数 $x_j$ 和 $y_j$（$0 \le x_j \le y_j \le N$）。

在全部 25 分中，有 5 分满足 $x_j = y_j = 1$ 且 $N, M, K \le 4000$。

在全部 25 分中，另有 5 分满足 $x_j = y_j = 1$ 且 $N, M, c_i \le 4000$。

在全部 25 分中，另有 5 分满足 $x_j = y_j = 1$。

在全部 25 分中，另有 5 分满足 $x_j = 0$。

输出格式

输出 $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

样例说明 1

一个可行的购物计划必须将恰好一件花费在 $\{5, 3, 6\}$ 中的物品与恰好一件花费在 $\{3, 1\}$ 中的物品组合起来。