P4698 [CEOI 2011] Hotel

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.

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 one integer, the maximum profit. Note that the answer may be very large.

**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