Mineral Quality Inspection

Little T is a quality inspector tasked with examining a batch of minerals. The batch consists of n minerals numbered from 1 to n. Each mineral has a weight w_i and a value v_i. The inspection procedure is as follows:

1. Given m intervals \([l_i, r_i]\).
2. Select a parameter \(W\).
3. For an interval \([l_i, r_i]\), compute the inspection value \[ y_i = \Big(\sum_{j=l_i}^{r_i}[w_j \ge W]\Big) \times \Big(\sum_{j=l_i}^{r_i}[w_j \ge W]v_j\Big), \] where \([w_j \ge W]\) is 1 if \(w_j\) is at least \(W\) and 0 otherwise.

The overall inspection result is defined as

\[ y = \sum_{i=1}^{m} y_i. \]

If this inspection result differs too much from the standard value \(s\), another batch must be inspected. In order to avoid extra work, Little T wants to adjust the parameter \(W\) so that \(|s - y|\) is minimized. Your task is to help him find the minimum possible value of \(|s - y|\).

inputFormat

The first line contains three integers \(n\), \(m\), and \(s\) representing the number of minerals, the number of intervals, and the standard inspection value respectively.

The second line contains \(n\) integers \(w_1, w_2, \ldots, w_n\) representing the weights of the minerals.

The third line contains \(n\) integers \(v_1, v_2, \ldots, v_n\) representing the values of the minerals.

The following \(m\) lines each contain two integers \(l_i\) and \(r_i\) (with \(1 \le l_i \le r_i \le n\)), representing an interval.

outputFormat

Output a single integer -- the minimum possible value of \(|s - y|\) achievable by choosing an appropriate \(W\).

sample

5 3 100
3 5 2 6 4
1 2 3 4 5
1 3
2 5
3 5

20

</p>