시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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}.