Problem Description

You run a hotel with $n$ rooms. Each room has a maintenance cost and a capacity. For room $i$, the maintenance cost is $c_i$ and the capacity is $p_i$ people.

There are $m$ orders. Each order has two parameters: $v_i, d_i$, where $v_i$ is the rent paid by the order, and $d_i$ is the number of people.

You need to choose some orders and reject the others, so that each chosen order is assigned to exactly one room, and its number of people does not exceed the capacity of that room. Of course, two different orders cannot be assigned to the same room.

You want to know the maximum profit when you choose at most $o$ orders. The profit of a plan is defined as the sum of rents of the chosen orders minus the sum of maintenance costs of the chosen rooms.

Input Format

The first line contains three integers $n, m, o$ separated by spaces.

The next $n$ lines each contain two integers $c_i, p_i$ separated by spaces.

The next $m$ lines each contain two integers $v_i, d_i$ separated by spaces.

Output Format

Output one integer, the maximum profit. Note that the answer may be very large.

3 2 2
150 2
400 3
100 2
200 1
700 3

400

Hint

Explanation for Sample $1$.

You can assign the first order to the third room, and the second order to the second room.

Constraints

For $100\%$ of the testdata, $1 \le n, m \le 500\ 000$, $1 \le o \le \min(n, m)$, $1 \le c_i, p_i, v_i, d_i \le 10^9$. It is guaranteed that for all $1 \le i, j \le n$, if $p_i \lt p_j$, then $c_i \le c_j$.

Translated by ChatGPT 5