쇼핑 계획

당신은 총 $N$개의 물건을 파는 가게에서 쇼핑하고 있다. $i$번째 물건의 종류는 $1$ 이상 $M$ 이하의 정수 $a_i$이고, 비용은 $c_i$이다. 가능한 쇼핑 계획은 물건들의 부분집합으로, 모든 종류 $j$에 대해 종류가 $j$인 물건의 개수가 구간 $[x_j, y_j]$에 속하는 것이다.

쇼핑 계획의 비용은 그 계획에 담긴 물건 비용의 합이다. 가능한 쇼핑 계획 중 비용이 가장 작은 $K$개의 비용을 구하라. 서로 다른 두 쇼핑 계획의 비용이 같으면 출력에서 별개로 센다.

첫 줄에 공백으로 구분된 세 정수 $N$, $M$, $K$가 주어진다 ($1 \le N, M, K \le 200000$). 이어서 $N$개의 줄에 각각 공백으로 구분된 두 정수 $a_i$와 $c_i$가 주어진다 ($1 \le a_i \le M$, $1 \le c_i \le 10^9$). 이어서 $M$개의 줄에 각각 공백으로 구분된 두 정수 $x_j$와 $y_j$가 주어진다 ($0 \le x_j \le y_j \le N$).

$K$개의 줄을 출력한다. $i$번째 줄에는 $i$번째로 비용이 작은 가능한 쇼핑 계획의 비용을 출력한다. 가능한 쇼핑 계획이 $i$개보다 적으면 $-1$을 출력한다.

가능한 쇼핑 계획은 비용이 $\{5, 3, 6\}$에 속하는 물건 중 정확히 하나와 비용이 $\{3, 1\}$에 속하는 물건 중 정확히 하나를 반드시 포함해야 한다.