Hotel

A friend runs a hotel by the sea. As the peak season begins, reservation requests pour in, so your friend asks you to build the reservation system.

The hotel has $n$ rooms available. Room $i$ costs your friend an upkeep of $c_i$ but only when it is rented, and it holds up to $p_i$ people. Upkeep is monotone in capacity: a room's upkeep is never cheaper than the upkeep of any room that holds fewer people.

The system receives many requests. Request $j$ specifies the amount $v_j$ offered to rent one room for a single day, together with the minimum capacity $d_j$ of the room it asks for. Each request may be assigned to at most one room, and each room may serve at most one request; an assigned room must have capacity at least the request's minimum. Your friend will accept at most $o$ requests.

Compute the maximum profit your friend can make (total rent collected minus the upkeep of the rooms actually used) by accepting some of the requests.

The first line contains three integers $n$, $m$, and $o$ ($1 \le n, m \le 500,000$, $1 \le o \le \min(m, n)$): the number of rooms, the number of requests received, and the maximum number of requests your friend will accept.

The next $n$ lines describe the rooms; the $i$-th contains two integers $c_i$ and $p_i$ ($1 \le c_i, p_i \le 10^9$), the upkeep and the capacity of the room.

The next $m$ lines describe the requests; the $j$-th contains two integers $v_j$ and $d_j$ ($1 \le v_j, d_j \le 10^9$), the offered rent and the requested minimum capacity.

Print a single integer: the maximum profit obtainable by accepting at most $o$ requests. Print $0$ if accepting nothing is best. The profit may be large.