E. Спидран
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы играете в компьютерную игру, в которой есть $$$n$$$ заданий, которые вам нужно выполнить. Однако $$$j$$$-е задание можно выполнить только в начале $$$h_j$$$-го часа игрового дня. Каждый игровой день длится ровно $$$k$$$ часов. Часы каждого игрового дня пронумерованы числами $$$0, 1, \ldots, k - 1$$$. После конца первого дня начинается следующий, и так далее.

Между заданиями есть зависимости: для некоторых пар $$$(a_i, b_i)$$$ задание с номером $$$b_i$$$ может быть выполнено только после выполнения задания с номером $$$a_i$$$. Гарантируется, что циклических зависимостей нет, поскольку иначе игру пройти было бы невозможно и никто не стал бы в неё играть.

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

Найдите наименьшее время, за которое можно пройти игру.

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

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

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1\le n\le 200\,000$$$, $$$0\le m\le 200\,000$$$, $$$1\le k\le 10^9$$$) — количество заданий, количество зависимостей между ними, а также длительность игрового дня в часах.

Следующая строка содержит $$$n$$$ целых чисел $$$h_1, h_2, \ldots, h_n$$$ ($$$0\le h_i < k$$$).

Следующие $$$m$$$ строк описывают зависимости. В $$$i$$$-й из них содержатся два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1\le a_i < b_i\le n$$$): это означает, что задание с номером $$$b_i$$$ может быть выполнено только после выполнения задания $$$a_i$$$. Гарантируется, что все зависимости попарно различны.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$200\,000$$$.

Гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$200\,000$$$.

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

Для каждого набора входных данных выведите одно число — наименьшее время, необходимое для прохождения игры.

Пример
Входные данные
6
4 4 24
12 16 18 12
1 2
1 3
2 4
3 4
4 3 10
2 6 5 9
1 4
2 4
3 4
2 1 10
5 5
1 2
5 0 1000
8 800 555 35 35
5 0 10
3 2 5 4 7
3 2 5
4 3 2
1 2
2 3
Выходные данные
24
7
0
480
5
8
Примечание

В первом наборе входных данных задания $$$1$$$ и $$$4$$$ нужно выполнить в начале $$$12$$$-го часа дня, но они не могут быть выполнены в течение одного часа, поскольку между ними нужно выполнить задания $$$2$$$ и $$$3$$$. Однако всё это можно сделать за $$$24$$$ часа. Для этого можно начать в $$$12$$$ часов первого игрового дня, выполнив первое задание. В $$$16$$$ часов можно выполнить задание $$$2$$$. В $$$18$$$ часов можно выполнить задание $$$3$$$. Наконец, в $$$12$$$ часов следующего дня можно выполнить задание $$$4$$$. С момента выполнения первого задания до момента выполнения последнего прошло $$$24$$$ часа.

В третьем наборе входных данных можно выполнить первое задание, а затем сразу же выполнить второе. Можно начать в $$$5$$$ часов первого дня, выполнив первое задание. Сразу после этого становится доступным второе задание, его можно выполнять немедленно. Суммарное прошедшее время равно $$$0$$$.

В четвёртом наборе входных данных можно начать с третьего задания. Можно начать в $$$555$$$ часов первого дня и закончить в $$$35$$$ часов второго дня. Суммарное прошедшее время равно $$$1035-555=480$$$.