题目描述

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

输出格式

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

样例

input

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

output

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$。