Description

Xiao T is a quality inspector in charge of checking a batch of ores. There are $n$ ores, numbered from $1$ to $n$. Each ore has a weight $w_i$ and a value $v_i$. The inspection process is:

1. Given $m$ intervals $[l_i, r_i]$.
2. Choose a parameter $W$.
3. For an interval $[l_i, r_i]$, compute the inspection value $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$$

Here $j$ is the ore index, and $[p]$ is the indicator function: it returns $1$ if condition $p$ is true, and $0$ otherwise.

The overall inspection result $y$ for this batch is the sum of inspection values over all intervals, i.e., $\sum\limits_{i=1}^m y_i$.

If the overall inspection result differs too much from the given standard value $s$, another batch must be inspected. Xiao T wants to avoid extra work, so he will adjust the parameter $W$ to make the result as close to $s$ as possible, i.e., minimize $|s - y|$. Please compute this minimum value.

Input Format

The first line contains three integers $n, m, s$, denoting the number of ores, the number of intervals, and the standard value.

The next $n$ lines each contain two integers separated by a space. The $(i+1)$-th line gives the weight $w_i$ and value $v_i$ of ore $i$.

The next $m$ lines describe the intervals. Each line contains two integers separated by a space. The $(n+i+1)$-th line gives the endpoints $l_i$ and $r_i$ of interval $[l_i, r_i]$. Note: different intervals may coincide or overlap.

Output Format

Output a single integer, the minimum value required.

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

10

Hint

Explanation for the sample input and output:

When $W$ is $4$, the inspection values on the three intervals are $20$, $5$, $0$, so the overall result is $25$. The minimum difference from the standard value $s$ is $10$.

Constraints:

• For $10\%$ of the testdata, $1 \le n, m \le 10$.
• For $30\%$ of the testdata, $1 \le n, m \le 500$.
• For $50\%$ of the testdata, $1 \le n, m \le 5{,}000$.
• For $70\%$ of the testdata, $1 \le n, m \le 10{,}000$.
• For $100\%$ of the testdata, $1 \le n, m \le 200{,}000$, $0 < w_i, v_i \le 10^6$, $0 < s \le 10^{12}$, $1 \le l_i \le r_i \le n$.

Translated by ChatGPT 5