题目背景

小源是某代公司的产品设计师，这次的任务是负责设计一个PB限定高达套装。

题目描述

公司有一批板件，共有 $n$ $(1 ≤ n ≤ 200,000)$种，编号从 $1$ 到 $n$。每种板件都有一个重要度 $w_i$ 和价值 $v_i$。$(0 < w_i, v_i ≤ 10^6)$

每个高达模型使用一个连续的板件区间 $[l_i, r_i]$ $(1 ≤ l_i ≤ r_i ≤ n)$ 中的部分板件来组装。为了控制套装的整体成本，小源设定了一个重要度阈值 $W$，只有重要度不低于 $W$ 的板件才会被使用。

对于每个高达模型 $i$，其模型价值 $y_i$ 计算如下：

$$y_i=\sum\limits_{j=l_i}^{r_i}[w_j \ge W] \times \sum\limits_{j=l_i}^{r_i}[w_j \ge W]v_j $$

其中 $[w_j \ge W]$ 是指示函数，若条件为真返回 $1$，否则返回 $0$。

套装包含了 $m$ $(1 ≤ m ≤ 200,000)$个不同的高达模型，整个套装的总价值是所有高达模型的价值之和：$y=\sum\limits_{i=1}^m y_i$。

根据市场策略，公司希望套装的总价值尽可能接近目标价值 $s$ $(0 < s ≤ 10^{12})$，即最小化 $|s-y|$。请你帮助小源确定重要度阈值 $W$，使得 $|s-y|$ 最小。

所有数据满足：$n\times m\times \sum\limits_{j=1}^{n}v_j ≤ 5 \times 10^{18}$

输入格式

第一行包含三个整数 $n,m,s$，分别表示板件的种类数、高达模型的个数和目标价值。

接下来的 $n$ 行，每行两个整数，中间用空格隔开，第 $i+1$ 行表示 $i$ 号板件的重要度 $w_i$ 和价值 $v_i$。

接下来的 $m$ 行，表示每个高达模型使用的板件区间，每行两个整数，中间用空格隔开，第 $i+n+1$ 行表示区间 $[l_i,r_i]$ 的两个端点 $l_i$ 和 $r_i$。

输出格式

一个整数，表示 $|s-y|$ 的最小值。

样例

输入数据1

5 3 15 
1 5 
2 5 
3 5 
4 5 
5 5 
1 5 
2 4 
3 3

输出数据1

10

样例解释

当 $W$ 选 $4$ 的时候，

$$y_1 = 2 \times ( 5 + 5 ) = 20$$ $$y_2 = 1 \times 5 = 5$$ $$y_3 = 0 \times 0 = 0$$

总价值为 $25$，此时与目标价值 $15$ 相差最小为 $10$。