P1314 [NOIP 2011 Senior] Smart Quality Inspector

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.

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 a single integer, the minimum value required.

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