旅馆 ### 题目描述 你经营着一家旅馆，这家旅馆有 $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\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$。 ### 输出描述 输出一行一个整数表示最大收益。注意答案可能很大。 ### 输入输出样例 #### 示例 1 >输入 ```txt 3 2 2 150 2 400 3 100 2 200 1 700 3 ``` >输出 ```txt 400 ```