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

Автор:И. Блинов, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N, P ≤ 105, 0 ≤ K ≤ 105, 1 ≤ wi, mi ≤ 109, 1 ≤ ti ≤ P

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
1501 ≤ N, P ≤ 102, 0 ≤ K ≤ 102полная
2501 ≤ N, P ≤ 105, 0 ≤ K ≤ 1051полная

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 5 2
5 6
1 1 1 1 1 1 1 2 1 2
NO
2
2 2 1
3 6
3 1 6 2
YES

0.137s 0.028s 13