У Камиля на рабочем столе находятся $$$n$$$ листов бумаги, пронумерованных от $$$1$$$ до $$$n$$$. Чтобы было комфортно писать на $$$i$$$-м листе бумаги, надо чтобы на него попадало как минимум $$$a_i$$$ света. Для того, чтобы освещать листы, у Камиля есть $$$q$$$ ламп, $$$j$$$-я лампа освещает листы с номерами от $$$l_j$$$ до $$$r_j$$$. Если на $$$j$$$-ю лампу подать $$$x$$$ электричества, то освещённость каждого листа бумаги с номером $$$i$$$, где $$$l_j \le i \le r_j$$$, увеличится ровно на $$$x$$$.
Камиль не любит просто так тратить электричество, поэтому он просит вас найти такой минимальный $$$x$$$, что если подать на каждую лампу ровно $$$x$$$ электричества, то ему будет комфортно писать на хотя бы $$$k$$$ листах бумаги. Изначально освещенность каждого листа равна нулю.
В первой строке дано два целых числа $$$n$$$ и $$$k$$$ $$$(1 \le k \le n \le 10^5)$$$ — количество листов бумаги на рабочем столе и количество листов бумаги, которые необходимо осветить, соответственно.
Во второй строке дано $$$n$$$ целых чисел $$$a_1,\ a_2,\ a_3,\ \ldots,\ a_n$$$ $$$(0 \le a_i \le 10^9)$$$, где $$$a_i$$$ — необходимый уровень освещенности для $$$i$$$-го листа бумаги.
В третьей строке дано целое число $$$q$$$ $$$(1 \le q \le 10^5)$$$ — количество ламп.
В следующих $$$q$$$ строках описываются сами лампы, в $$$j$$$-й строке дано два целых числа $$$l_j$$$ и $$$r_j$$$ $$$(1 \le l_j \le r_j \le n)$$$ — границы отрезка листов бумаг, которые освещает $$$j$$$-я лампа.
Выведите одно минимальное целое неотрицательное число $$$x$$$, что если подать на каждую лампу по $$$x$$$ электричества, то будет комфортно писать на хотя бы $$$k$$$ листах бумаги. Если такого $$$x$$$ не существует, выведите $$$-1$$$.
Тесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп.
| Группа | Баллы | Дополнительные ограничения | Необходимые группы | Комментарий |
| 0 | 0 | — | — | Тесты из условия |
| 1 | 25 | $$$n \le 100,\ q \le 100,\ a_i \le 100$$$ | — | В этой группе $$$a_i \le 100$$$, то есть необходимый уровень освещенности каждого листа не больше $$$100$$$. |
| 2 | 20 | $$$n \le 1000,\ q \le 1000,\ k = n$$$ | — | |
| 3 | 30 | $$$q = 1$$$ | — | |
| 4 | 25 | — | 0, 1, 2, 3 | Полные ограничения |
6 37 5 9 8 3 622 44 6
5
10 910 8 9 5 3 1 6 7 4 233 51 47 9
-1
В первом примере первая лампа отвечает за листы $$$2,\ 3,\ 4$$$, а вторая — за $$$4,\ 5,\ 6$$$. Если подать $$$x = 5$$$ электричества на каждую лампу, то освещённости листов станут равны $$$0,\ 5,\ 5,\ 10,\ 5,\ 5$$$ соответственно. В этом случае листы $$$2,\ 4,\ 5$$$ получат необходимую освещенность. Можно показать, что при $$$x \lt 5$$$ не получится осветить хотя бы $$$3$$$ листа необходимым образом.
