[CEOI2011] Hotel

内存限制：256 MB 时间限制：4000 ms

Your friend owns a hotel at the seaside in Gdynia. The summer season is just starting and he is overwhelmed by the number of oﬀers from potential customers. He asked you for help in preparing a reservation system for the hotel.

There are $n$ rooms for rent in the hotel, the $i$-th room costs your friend $c_i$ zlotys of upkeep (only if it is rented) and has a capacity of $p_i$ people. You may assume that the upkeep of a room is never cheaper than the upkeep of any smaller room, that is, of any room which can hold a smaller number of people.

The reservation system will be receiving multiple oﬀers, each of them specifying the amount of zlotys for rental of any room ($v_j$) for one particular day and the minimal capacity of the requested room ($d_j$). For each oﬀer, only a single room can be rented. And conversely: each room can accommodate only a single oﬀer. Your friend has decided not to accept more than $o$ oﬀers.

Knowing you are a skilled programmer, your friend asked you to implement the part of the system which ﬁnds the maximum proﬁt (total income from renting out rooms minus their upkeep) he can make by accepting some of the oﬀers.

The ﬁrst line of the standard input contains three integers $n$, $m$, and $o$ ($1 \le n,m \le 500000, 1 \le o \le \min(m,n)$), denoting the number of rooms in the hotel, the number of oﬀers received and the maximum number of oﬀers your friend is willing to accept. The next $n$ lines describe the rooms, with the $i$-th of these lines containing two integers $c_i$, $p_i$ representing the upkeep of the room in zlotys and the capacity of the room ($1 \le c_i,p_i \le 10^9$). The next m lines describe the oﬀers, with the $j$-th of these lines containing two integers $v_j, d_j$ representing the oﬀered rental price in zlotys and the minimal capacity of the requested room ($1 \le v_j,d_j \le 10^9$).

You may assume that in test cases worth 40 points in total an additional inequality $n,m \le 100$ holds.

The ﬁrst and only line of the standard output should contain one integer equal to the maximum proﬁt your friend can achieve accepting at most $o$ of the oﬀers. Note that the proﬁt might get big.

样例输入 1

样例输出 1

Explanation of the example: Your friend can accept both oﬀers, renting out rooms number 2 and 3.

C0532 [CEOI2011] Hotel

题目描述

输入格式

输出

样例

样例输入 1

样例输出 1

提示