시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 6 3 3 50.000%

## 문제

You are shopping from a store that sells a total of N items. The i-th item has a type ai which is an integer between 1 and M. A feasible shopping plan is a subset of these items such that for all types j, the number of items of type j is in the interval [xj, yj].

The i-th item in the store has a cost of ci, and the cost of a shopping plan is the sum of the costs of items in the plan. You are interested in the possible costs of feasible shopping plans. Find the costs of the K cheapest feasible shopping plans. Note that if there are two different shopping plans with the same cost, they should be counted separately in the output.

## 입력

The first line consists of three space-separated integers N, M, and K (1 ≤ N, M, K ≤ 200 000). N lines follow, the i-th of which contains two space-separated integers ai and ci (1 ≤ ai ≤ M, 1 ≤ ci ≤ 109). M lines follow, the j-th of which contains two space-separated integers xj and yj (0 ≤ xj ≤ yj ≤ N).

## 출력

Output K lines. On the i-th line, output the cost of the i-th cheapest feasible shopping plan, if one exists, or -1 if there are fewer than i feasible shopping plans.

## 예제 입력 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


## 힌트

A feasible shopping plan must combine exactly one item with a cost in {5, 3, 6} with exactly one item with a cost in {3, 1}.