Задача C. Контроль за выловом рыбы ≡

Условие

Всего для вылова доступно P видов рыб. Известно, что компания владелец рыболовного судна получила квоты на вылов w_i килограмм i-го вида рыбы.

Рыболовное судно выловило N рыб, i-я рыба имеет вес m_i. Каждая из выловленных рыб отнесена к одному из P видов.

Рыбинспектор хочет провести проверку. Он знает, что недобросовестные рыболовы могли поменять местами некоторые рыбы для занижения количества выловленной рыбы какого-либо вида. Однако инспектор точно знает, что не более чем K рыб были перемещены в другую категорию, иначе он сразу бы заметил подмену.

Рыбиспектор хочет узнать, могло ли случиться так, что какого-то вида рыбы было выловлено больше, чем разрешено по квоте.

Формат входного файла

Первая строка входного файла содержит целые числа P, N, K. Во второй строке содержится P целых чисел w_i — размер квоты в килограммах на вылов рыбы вида i. В третьей строке содержится N пар целых чисел m_i и t_i — масса и вид, к которому отнесли рыбу с номером i рыболовы.

Формат выходного файла

Выходной файл должен содержать строку "NO", если рыболовы точно не нарушили ограничения по квотам. В противном случае "YES".

Ограничения

1 ≤ N, P ≤ 10⁵, 0 ≤ K ≤ 10⁵, 1 ≤ w_i, m_i ≤ 10⁹, 1 ≤ t_i ≤ P

Описание подзадач и системы оценивания

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

Примеры тестов

2 5 2
5 6
1 1 1 1 1 1 1 2 1 2

NO

2 2 1
3 6
3 1 6 2

YES