D. Закулисье ICPC
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы исследуете Закулисье и сейчас застряли в одной очень странной аномалии. После кропотливых исследований вы поняли, что тут недавно прошёл командный контест ICPC формата.

Вам удалось выяснить, что в контесте участвовали $$$n$$$ команд и было $$$m$$$ задач. Также сохранился журнал всех посылок команд в хронологическом порядке, однако вердикты не сохранились. Посылка с вердиктом «принято» означает, что команда решила соответствующую задачу. После этого команда могла продолжать отправлять посылки по той же задаче, но они уже ни на что не влияли. Известно, что команда $$$i$$$ решила ровно $$$p_i$$$ различных задач.

За каждую задачу команда, решившая её первой, получает одну звёздочку (aka first-to-solve). Задача, которую никто не решил, не приносит звёздочку никому.

Для выхода из аномалии вам осталось ответить на один очень странный вопрос: какое минимальное количество звёздочек могла получить команда номер $$$1$$$?

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ — количество наборов входных данных $$$(1 \leq t \leq 1000)$$$. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ — количество команд, задач и посылок соответственно $$$(1 \leq n \leq 1000,\; 1 \leq m \leq 1000,\; 1 \leq k \leq 10^5)$$$.

Во второй строке каждого набора даны $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$, где $$$p_i$$$ — количество различных задач, решённых командой $$$i$$$ $$$(0 \leq p_i \leq m)$$$.

В следующих $$$k$$$ строках даны два целых числа $$$i$$$ и $$$j$$$ — номер команды и номер задачи для каждой посылки $$$(1 \leq i \leq n,\; 1 \leq j \leq m)$$$. Посылки перечислены в хронологическом порядке: каждая следующая была отправлена позже предыдущей.

Гарантируется, что в каждом наборе существует хотя бы один способ назначить вердикты посылкам так, чтобы каждая команда $$$i$$$ решила ровно $$$p_i$$$ задач.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$, сумма $$$m$$$ не превосходит $$$1000$$$, а сумма $$$k$$$ не превосходит $$$10^5$$$.

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

Для каждого набора выведите одно целое число — минимальное количество звёздочек, которое могла получить команда номер $$$1$$$.

Пример
Входные данные
3
1 1 1
1
1 1
3 3 5
1 1 1
2 1
1 1
1 2
3 2
3 3
3 4 7
2 1 1
2 1
1 1
2 2
1 2
3 2
1 3
1 4
Выходные данные
1
0
1