어수선한 공연

아르투르 플렉이 머레이 쇼에 초대받았다. 그는 공연을 빠르게 계획했다. 하지만 경찰에게 잡히지 않도록 도주 계획도 세워야 한다.

쇼에는 관객 $n$명과 경찰 $m$명이 온다. 관객은 한 줄로 앉으며, 왼쪽에서 오른쪽으로 1번부터 $n$번까지 번호가 매겨진다. 경찰도 1번부터 $m$번까지 번호가 매겨진다. $i$번 경찰은 아르투르를 감시하면서, 관객 $l_i$번부터 $r_i$번까지(양 끝 포함) 소란이 없는지도 살핀다. 관객 $j$는 처음에 0 이상의 품위 수준 $a_j$를 가진다. $i$번 경찰이 아르투르에게 보이는 주의 수준은 그가 감시하는 관객들의 품위 수준을 모두 더한 값이다. 관객의 품위가 낮을수록 경찰은 무대 대신 그들을 살펴야 한다.

쇼 전에 아르투르는 일부 관객을 만나 카리스마로 그들의 품위 수준을 낮춘다. 품위 수준은 양의 정수 단위로 낮출 수 있다. 어떤 관객의 품위 수준도 음수가 될 수 없다. 아르투르의 카리스마로 낮출 수 있는 합계는 최대 $k$까지다. 아르투르가 달성할 수 있는 경찰들의 주의 수준 합의 최솟값을 구하라.

첫 줄에 관객 수 $n$, 경찰 수 $m$, 아르투르가 품위 수준을 낮출 수 있는 합계의 최대값 $k$가 주어진다 ($1 \le n \le 10^5$, $1 \le m \le 10^6$, $0 \le k \le 10^{12}$).

둘째 줄에는 관객들의 초기 품위 수준 $a_i$가 $n$개 주어진다 ($0 \le a_i \le 10^7$).

다음 $m$개 줄에는 각각 두 정수 $l_i$와 $r_i$가 주어진다. 이는 $i$번 경찰이 $l_i$번 관객부터 $r_i$번 관객까지(양 끝 포함) 감시한다는 뜻이다 ($1 \le l_i \le r_i \le n$).

아르투르가 달성할 수 있는 경찰들의 주의 수준 합의 최솟값을 한 줄에 출력한다.