19616번 - Shopping Plans 다국어

문제

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 [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.

입력

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 a_i and c_i (1 ≤ a_i ≤ M, 1 ≤ c_i ≤ 10⁹). M lines follow, the j-th of which contains two space-separated integers x_j and y_j (0 ≤ x_j ≤ y_j ≤ 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.

제한

힌트

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}.