После того, как Артура Флека пригласили на шоу Мюррея, он быстро спланировал свое выступление. Однако, также ему нужно продумать план отступления, чтобы его не поймала полиция.
Ему известно, что на шоу придет $$$n$$$ зрителей и $$$m$$$ сотрудников полиции. Зрители на шоу сядут в один ряд, для удобства пронумеруем их от $$$1$$$ до $$$n$$$ слева направо, а сотрудников полиции пронумеруем от $$$1$$$ до $$$m$$$. Сотрудник полиции номер $$$i$$$ будет следить, как за Артуром, так и за отсутствием беспорядков среди зрителей с номерами от $$$l_i$$$ до $$$r_i$$$ включительно. Зритель номер $$$j$$$ изначально имеет неотрицательный уровень порядочности $$$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}$$$).
Во второй строке даны $$$n$$$ целых чисел $$$a_i$$$ — начальные значения уровней порядочности зрителей ($$$0 \le a_i \le 10^7$$$).
В следующих $$$m$$$ строках дано по два числа $$$l_i$$$ и $$$r_i$$$, означающие, что $$$i$$$-й полицейский следит за зрителями с номерами от $$$l_i$$$ до $$$r_i$$$ включительно ($$$1 \le l_i \le r_i \leqslant n$$$).
В единственной строке выведите одной целое число — минимальная сумма уровней внимания полицейских, которой может добиться Артур.
4 2 2 1 2 3 4 1 4 3 4
13
4 2 5 1 2 0 0 1 4 3 4
0