你的朋友在格丁尼亚（Gdynia）的海边拥有一家旅馆。夏季刚刚开始，他被潜在客户的大量预订请求搞得应接不暇。他请求你帮他为旅馆制作一个预订系统。

旅馆有 $n$ 间客房可供出租，第 $i$ 间客房的维护成本为 $c_i$ 兹罗提（zlotys）（仅在出租时产生），容纳人数为 $p_i$ 人。你可以假设，任何房间的维护成本绝不会低于任何容纳人数更小的房间的维护成本。也就是说，容纳人数较小的房间，其维护成本不会高于容纳人数较大的房间。

预订系统将收到多个订单，每个订单指定了租用任意房间一天的出价（$v_j$ 兹罗提）以及所请求房间的最小容纳人数（$d_j$）。对于每个订单，只能租用一间房。反之亦然：每间房只能接待一个订单。你的朋友决定最多接受 $o$ 个订单。

知道你是一位优秀的程序员，你的朋友请你实现系统的一部分，该部分通过接受其中的一些订单，来计算他能获得的最大利润（出租房间的总收入减去它们的维护成本）。

输入格式

第一行包含三个整数 $n$、$m$ 和 $o$（$1 \le n, m \le 500\,000$，$1 \le o \le \min(m, n)$），分别表示旅馆的房间数、收到的订单数以及你的朋友愿意接受的最大订单数。

接下来的 $n$ 行描述房间，其中第 $i$ 行包含两个整数 $c_i$ 和 $p_i$，代表该房间的维护成本（兹罗提）和容纳人数（$1 \le c_i, p_i \le 10^9$）。

接下来的 $m$ 行描述订单，其中第 $j$ 行包含两个整数 $v_j$ 和 $d_j$，代表该订单的出价（兹罗提）和所请求房间的最小容纳人数（$1 \le v_j, d_j \le 10^9$）。

对于占总分 $40\%$ 的测试用例，还满足附加限制 $n, m \le 100$。

输出格式

输出的第一行也是唯一一行应该包含一个整数，表示你的朋友通过接受最多 $o$ 个订单所能获得的最大利润。注意，利润可能会很大。

样例

输入样例 1

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

输出样例 1

400

说明

你的朋友可以接受两个订单，分别出租 2 号和 3 号房间。