В Челябинске открыли новую обсерваторию, и Лосяш переехал туда, чтобы заниматься астрономией.
Лосяш наблюдает за $$$n$$$ космическими объектами, расположенными подряд друг за другом в одном ряду. $$$i$$$-й по счёту объект по наблюдениям Лосяша имеет целочисленную массу $$$a_i$$$. Космические объекты входят в $$$m$$$ галактик, где каждая галактика является непрерывным отрезком космических объектов. Более формально, $$$j$$$-ю галактику можно представить с помощью двух чисел $$$l_j$$$ и $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$), обозначающих, что все объекты с номерами $$$i$$$ такими, что $$$l_j \le i \le r_j$$$, входят в $$$j$$$-ю галактику. Заметьте, что галактики могут пересекаться между собой.
Массой галактики является сумма всех объектов, входящих в неё, т.е. масса галактики $$$j$$$ будет равна $$$\sum_{i=l_j}^{r_j} a_i$$$. Масса Вселенной равна максимальной массе из $$$m$$$ галактик, за которыми наблюдает Лосяш.
Лосяш знает, что один из наблюдаемых космических объектов является чёрной дырой, масса которой может быть абсолютно любой. Коллега Лосяша подсказала ему, что масса и расположение чёрной дыры являются такими, чтобы масса Вселенной была минимально возможной. Зная, что один из $$$n$$$ наблюдаемых объектов на самом деле является чёрной дырой и может иметь любую массу, помогите Лосяшу узнать массу Вселенной.
В первой строке входных данных содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наблюдений Лосяша. Далее следуют описания наблюдений.
В первой строке каждого наблюдения содержится два целых числа $$$n$$$ и $$$m$$$ ($$$1\le n,m \le 2\cdot 10^5$$$) — количество космических объектов и галактик соответственно.
Во второй строке каждого наблюдения содержится $$$n$$$ целых чисел $$$a_i$$$ ($$$-10^9 \le a_i \le 10^9$$$) — предполагаемые массы космических объектов.
В следующих $$$m$$$ строках каждого наблюдения содержится по два целых числа, в $$$j$$$-й строке находятся числа $$$l_j$$$ и $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — границы $$$j$$$-й галактики.
Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ по всем наблюдениям не превышает $$$2 \cdot 10^5$$$.
Для каждого наблюдения Лосяша в отдельной строке выведите минимально возможную массу Вселенной, если она конечна, либо строку -inf, если масса Вселенной оказалась бесконечно малой.
35 3-10 2 10 5 74 51 13 35 3-7 -5 -9 -5 51 32 34 54 11 -1 4 31 3
10 -14 -inf