C. Лампы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Камиля на рабочем столе находятся $$$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$$$.

Система оценки

Тесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп.

ГруппаБаллыДополнительные ограниченияНеобходимые группыКомментарий
00——Тесты из условия
125$$$n \le 100,\ q \le 100,\ a_i \le 100$$$—В этой группе $$$a_i \le 100$$$, то есть необходимый уровень освещенности каждого листа не больше $$$100$$$.
220$$$n \le 1000,\ q \le 1000,\ k = n$$$—
330$$$q = 1$$$—
425—0, 1, 2, 3Полные ограничения
Примеры
Входные данные
6 3
7 5 9 8 3 6
2
2 4
4 6
Выходные данные
5
Входные данные
10 9
10 8 9 5 3 1 6 7 4 2
3
3 5
1 4
7 9
Выходные данные
-1
Примечание

В первом примере первая лампа отвечает за листы $$$2,\ 3,\ 4$$$, а вторая — за $$$4,\ 5,\ 6$$$. Если подать $$$x = 5$$$ электричества на каждую лампу, то освещённости листов станут равны $$$0,\ 5,\ 5,\ 10,\ 5,\ 5$$$ соответственно. В этом случае листы $$$2,\ 4,\ 5$$$ получат необходимую освещенность. Можно показать, что при $$$x \lt 5$$$ не получится осветить хотя бы $$$3$$$ листа необходимым образом.