Maximizing the Restored Operations

We are given an array (a) of length (n) and an auxiliary array (b) of length (n) initialized with zero. In addition, there are (m) operations. The (i)-th operation is originally specified by two integers (l_i) and (r_i) together with a forgotten value (v_i \in {-1, 1}). In the original (dream) version, an operation on a segment ([l,r]) would compute [ v' = v\Bigl(1-\max_{l \le i \le r} |b_i|\Bigr), ] then update every (b_i) (for (l\le i\le r)) by (b_i \leftarrow b_i + v'). After all operations are applied in some order the output would be [ \sum_{i=1}^n a_i b_i. ] \nHowever, our coach has forgotten the relative order of operations and the corresponding (v) values – he only recalls that each (v) is either (1) or (-1). Moreover, he is allowed to modify the interval endpoints of at most (k) operations. A single modification consists of shifting one endpoint by (\pm1) (i.e. replacing (l_i) by (l_i-1) or (l_i+1) or (r_i) by (r_i-1) or (r_i+1)) while always preserving (1 \le l_i \le r_i \le n). \nAfter these modifications and by appropriately choosing the order of operations and the sign (v) for each operation, the final value (\sum_{i=1}^n a_i b_i) is determined as follows. Note that since every operation is applied on indices that are still zero (because any index that has been updated to (\pm1) remains unchanged by later operations as (1-\max|b_i|=0)), each operation effectively assigns a constant value to a contiguous segment (its first occurrence in the order). In other words, our freedom allows us to select at most (m) disjoint segments and assign all indices in each segment the value (v) (either (1) or (-1)). By choosing (v=1) for a segment we add (\sum_{i=l}^r a_i) to the answer; by choosing (v=-1) we add (-\sum_{i=l}^r a_i), so the optimal contribution from a segment ([L,R]) is (|\sum_{i=L}^R a_i|). However, for each operation the interval can be modified from its original ([l_i,r_i]) to a new segment ([L,R]) at a modification cost of [ |L-l_i|+|R-r_i|. ]

The challenge is to choose some disjoint segments together with an assignment of operations (after sorting the operations in an arbitrary order) such that if the (j)-th operation (after sorting) originally has endpoints ((l_j, r_j)) and is used to cover ([L,R]), then a cost of (|L-l_j|+|R-r_j|) is incurred. The total modification cost must not exceed (k) and the sum of contributions (|\sum_{i=L}^{R} a_i|) over all chosen segments is maximized.

All original operation intervals are given with the guarantee that none is strictly contained in another (i.e. there do not exist indices (i) and (j) such that (l_i < l_j \le r_j < r_i)). This property holds before modifications; after modifications it may be broken.

Your task is to compute the maximum final answer achievable under the above rules.

Input Format: The first line contains three integers (n, m, k). The second line contains (n) integers (a_1, a_2, \dots, a_n). Each of the next (m) lines contains two integers (l_i) and (r_i), representing the original interval of the (i)-th operation.

Note: You are allowed to choose fewer than (m) operations if it is beneficial.

inputFormat

The first line contains three space‐separated integers: n m k.

The second line contains n space‐separated integers: a1 a2 ... an.

Each of the next m lines contains two space‐separated integers li ri, representing the original endpoints of the i-th operation's interval.

outputFormat

Output a single integer, the maximum possible value of \(\sum_{i=1}^n a_i b_i\) that can be achieved.

sample

5 2 2
1 -2 3 -4 5
1 3
4 5

3