题目描述

小 T 有 $n$ 个物品，第 $i$ 个物品的颜色为 $c_i$，权值为 $a_i$。

小 T 有 $m$ 个背包，第 $i$ 个背包里至少要装 $l_i$ 个物品，至多能装 $r_i$ 个物品，且第 $i$ 个背包中的物品的颜色必须为 $i$。

一个合法方案的权值是所有背包里的物品的权值和。

请求出权值前 $k$ 小的合法方案的权值。两个合法方案不同当且仅当存在一个物品在一个方案中被放进了背包，另一个方案中没被放进背包。

输入格式

第一行三个整数 $n,m,k$，表示物品数，背包数以及方案前几小。

接下来 $n$ 行，第 $i$ 行两个整数 $c_i,a_i$，表示第 $i$ 个物品的颜色和权值。

接下来 $m$ 行，第 $i$ 行两个整数 $l_i,r_i$，表示背包的容量下限和上限。

输出格式

输出 $k$ 行，第 $i$ 行一个整数，表示第 $i$ 小的答案，如果合法方案数小于 $i$，则输出 $-1$。

样例

样例输入 1

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

样例输出 1

5
7
7
7
7
8
9

样例输入 2

6 2 6
2 1
2 2
2 3
1 1
1 1
1 1
3 3
0 1

样例输出 2

3
4
5
6
-1
-1

数据范围

对于所有数据，$1\leq n,m,k\leq 2\times 10^5$，$1\leq c_i\leq m$，$1\leq a_i\leq 10^9$，$0\leq l_i\leq r_i\leq n$。

• 子任务 $1$（$15$ 分）：$n,m,k\leq 4000$，$l_i=r_i=1$。
• 子任务 $2$（$17$ 分）：$n,m,a_i\leq 4000$，$l_i=r_i=1$。
• 子任务 $3$（$25$ 分）：$l_i=r_i=1$。
• 子任务 $4$（$18$ 分）：$l_i=0$。
• 子任务 $5$（$25$ 分）：无特殊限制。