Canadian Computing Olympiad: 2020 Day 2, Problem 3

You are shopping from a store that sells a total of ~N~ items. The ~i~-th item has a type ~a_i~ 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 ~[x_j, y_j]~.

The ~i~-th item in the store has a cost of ~c_i~, 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.

Input Specification

The first line consists of three space-separated integers ~N~, ~M~, and ~K~ ~(1 \le N, M, K \le 200\,000)~. ~N~ lines follow, the ~i~-th of which contains two space-separated integers ~a_i~ and ~c_i~ ~(1 \le a_i \le M, 1 \le c_i \le 10^9)~. ~M~ lines follow, the ~j~-th of which contains two space-separated integers ~x_j~ and ~y_j~ ~(0 \le x_j \le y_j \le N)~.

For 5 of the 25 available marks, ~x_j = y_j = 1~ and ~N, M, K \le 4\,000~.

For an additional 5 of the 25 available marks, ~x_j = y_j = 1~ and ~N, M, c_i \le 4\,000~.

For an additional 5 of the 25 available marks, ~x_j = y_j = 1~.

For an additional 5 of the 25 available marks, ~x_j = 0~.

Output Specification

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.

Sample Input 1

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

Output for Sample Input 1

4
6
6
7
8
9
-1

Explanation of Output for Sample Input 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\}~.