#2514. 「CEOI2011」Hotel

内存限制:64 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: diamond_duke

题目描述

你经营着一家旅馆,这家旅馆有 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