You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

人生如同长河，从出生流向生命尽头。在这漫长的旅程中，我们会与许多人相逢，或短暂停留，或相伴许久。如果用时间轴描绘你的一生，那么每个相遇过的人，都可以看作时间轴上的一个区间。

你对过去的记忆是离散的，由若干个记忆点组成，而点亮每一个都需要相应的代价。尽管相逢可能短暂，但只要在产生交集的时间内，有被点亮的记忆点，那么这段相逢对你而言，就是有意义的。

形式化地说，你有 $n$ 个记忆点，第 $i$ 个位于时间轴的坐标 $x_i$，点亮它需要价值 $w_i$ 。你曾经与 $m$ 个人相遇，从 $0$ 到 $m-1$ 编号，第 $i$ 个人对应的区间是 $[l_i, r_i]$。我们说，一个人是值得回忆的，当且仅当其对应的区间内，至少有一个记忆点被点亮。

你拥有总价值 $W$，可以选择点亮一些记忆点。你的目标是在总消耗不超过 $W$ 的前提下，让值得回忆的人的编号的 $\operatorname{mex}$ 尽可能大。$\operatorname{mex}(S)$ 定义为集合 $S$ 中未出现的最小非负整数，特别地，$\operatorname{mex}(\emptyset) = 0$。

输入格式

第一行，输入 $n, m, W\,(1\le n, m \le 10^5, 1\le W \le 10^{14})$，含义与题面相同；

接下来 $n$ 行，每行两个数，表示 $x_i, w_i\,(1\le x_i, w_i \le 10^9)$；

接下来 $m$ 行，每行两个数，表示 $l_i, r_i\,(1\le l_i \le r_i \le 10^9)$，编号从 $0$ 开始。

输出格式

输出一行一个整数，表示值得回忆的人的编号的 $\operatorname{mex}$ 最大值。

输入输出样例 #1

输入 #1

4 6 10
2 3
3 7
8 2
15 1
4 10
11 15
1 2
14 16
3 3
8 15

输出 #1

4

说明/提示

选择点亮位于 $2,8,15$ 的记忆点，值得回忆的人的编号为 $0,1,2,3,5$，$\operatorname{mex}$ 值为 $4$ 。这三个记忆点缺少一个都会使 $\operatorname{mex}$ 值变小，且剩下的价值不足以点亮位于 $3$ 的记忆点，故最大的 $\operatorname{mex}$ 为 $4$ 。