[CEOI2011]Hotel

题目描述

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

输出格式


一行一个整数表示最大收益。注意答案可能很大。

输入输出样例

输入样例 #1

3 2 2
150 2
400 3
100 2
200 1
700 3

输出样例 #1

400

说明

**样例 $1$ 解释** 可以将第一个订单安排至第三个房间,将第二个订单安排至第二个房间。 **数据范围** 对于 $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$。