G. На балансе пусто
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Алисы есть карта для покупок с начальным балансом $$$h$$$. В супермаркете есть $$$n$$$ типов товаров. Товар типа $$$i$$$ стоит $$$c_i$$$, и Алиса может купить любое количество товаров каждого типа.

Также есть $$$m$$$ акций с возвратом части суммы. $$$j$$$-я акция применяется к покупке, если её общая стоимость не меньше $$$a_j$$$, и даёт возврат в размере $$$b_j$$$.

Для каждой покупки Алиса выполняет следующие действия:

  • Она выбирает один или несколько товаров, общая стоимость которых (обозначим её $$$x$$$) не превышает текущий баланс на карте, и оплачивает $$$x$$$ с карты.
  • Среди всех акций с возвратом, которые применяются к этой покупке, срабатывает та, у которой возврат максимален, и этот возврат добавляется к балансу карты. Если ни одна акция не применяется, возврат не добавляется.

Для каждого $$$h$$$ от $$$1$$$ до $$$s$$$ определите, может ли Алиса сделать баланс на карте равным $$$0$$$ после конечного числа покупок.

Входные данные

В первой строке заданы три целых числа $$$n$$$, $$$m$$$ и $$$s$$$ ($$$1 \le n, m, s \le 125\,000$$$) — количество типов товаров, количество акций с возвратом и максимальный начальный баланс для рассмотрения соответственно.

Во второй строке заданы $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 125\,000$$$) — цена товара каждого типа.

$$$i$$$-я из следующих $$$m$$$ строк содержит два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le 125\,000$$$) — порог суммы покупки и размер возврата $$$i$$$-й акции соответственно.

Гарантируется, что $$$a_1 \lt a_2 \lt \cdots \lt a_m$$$ и $$$b_1 \lt b_2 \lt \cdots \lt b_m$$$.

Выходные данные

Выведите $$$s$$$ строк. Для каждого $$$i$$$ ($$$1 \le i \le s$$$) выведите «YES», если Алиса может сделать баланс на карте равным $$$0$$$, когда начальный баланс равен $$$i$$$, и «NO» в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Примеры
Входные данные
2 1 15
4 7
8 4
Выходные данные
NO
NO
NO
YES
NO
NO
YES
YES
NO
NO
YES
YES
NO
YES
YES
Входные данные
5 3 25
4 8 12 16 20
6 8
7 9
8 10
Выходные данные
NO
NO
NO
YES
NO
NO
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
Примечание

В первом примере Алиса может сделать баланс равным $$$0$$$, когда начальный баланс равен $$$15$$$, следующим образом:

  • Она покупает по одному товару каждого типа на общую сумму $$$4 + 7 = 11$$$. Баланс уменьшается с $$$15$$$ до $$$4$$$.
  • Поскольку $$$11 \ge 8$$$, срабатывает возврат в размере $$$4$$$. Баланс увеличивается с $$$4$$$ до $$$8$$$.
  • Она покупает один товар первого типа за $$$4$$$. Ни одна акция не применяется, поэтому баланс уменьшается с $$$8$$$ до $$$4$$$.
  • Она снова покупает один товар первого типа за $$$4$$$. Ни одна акция не применяется, поэтому баланс уменьшается с $$$4$$$ до $$$0$$$.

Следовательно, $$$15$$$-я строка вывода первого примера — «YES».

Во втором примере, если начальный баланс равен $$$4$$$, Алиса может купить один товар первого типа за $$$4$$$. Поскольку $$$4 \lt 6$$$, ни одна акция не применяется, и баланс становится равным $$$0$$$. Следовательно, четвёртая строка вывода второго примера — «YES». Если начальный баланс равен $$$1$$$, ни один товар недоступен для покупки, поэтому первая строка — «NO».