4519: 「CEOI2011」Hotel
内存限制：64 MB
时间限制：4.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
你经营着一家旅馆，这家旅馆有 $n$ 个房间，每个房间有维护费用和容量。其中第 $i$ 个房间的维护费用为 $c_i$，容量为 $p_i$ 人。
现在有 $m$ 个订单，每个订单有两个参数：$v_i,d_i$ ，其中 $v_i$ 表示这个订单支付的租金，$d_i$ 表示人数。
你现在得要合理选择一些订单，并放弃其他订单，使得每个选择的订单被安排在同一间房间内，且人数不超过这个房间的容量限制。当然，两个不同的订单也不能被安排在同一间房间内。
现在你想要知道，在最多选出 $o$ 个订单时的最大收益。一个方案的收益的定义为，选出的订单的租金和，减去选出的房间的维护费用和。
输入
第一行三个空格隔开的整数 $n,m,o$ 。
接下来 $n$ 行，每行两个空格隔开的整数 $c_i,p_i$。
接下来 $m$ 行，每行两个空格隔开的整数 $v_i,d_i$。
输出
一行一个整数表示最大收益。注意答案可能很大。
样例输入 复制
3 2 2
150 2
400 3
100 2
200 1
700 3样例输出 复制
400提示
数据范围：对于 $40\%$ 的数据，有 $n,m\le 100$。 对于 $100\%$ 的数据，有 $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$，保证 $\forall 1\le i,j\le n$，若 $p_i\lt p_j$，则 $c_i\le c_j$。