D. Путь домой
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Известный фокусник Боря Будини путешествовал по стране $$$X$$$, которая состоит из $$$n$$$ городов. Однако случилось несчастье, и его обокрали в городе номер $$$1$$$. Теперь Будини предстоит нелегкий путь домой в город $$$n$$$.

Добираться он собирается самолетами. Всего в стране есть $$$m$$$ авиарейсов, $$$i$$$-й летит из города $$$a_i$$$ в город $$$b_i$$$ и стоит $$$s_i$$$ монет. Обратите внимание, что $$$i$$$-й рейс односторонний, то есть не может использоваться, чтобы добраться из города $$$b_i$$$ в город $$$a_i$$$. Чтобы им воспользоваться, Боря должен быть в городе $$$a_i$$$ и иметь на руках хотя бы $$$s_i$$$ монет (которые он потратит на перелет).

После ограбления у него осталось всего $$$p$$$ монет, однако он не отчаивается! Находясь в городе $$$i$$$, он может хоть каждый день организовывать представления, которые будут приносить ему по $$$w_i$$$ монет каждый.

Помогите фокуснику узнать, сможет ли он добраться до дома, а также какое минимальное количество представлений придется для этого организовать.

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

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

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

Во второй строке каждого набора входных даны $$$n$$$ целых чисел $$$w_1, w_2, \ldots, w_n$$$ $$$(1 \le w_i \le 10^9)$$$ — прибыль от представлений.

В следующих $$$m$$$ строках даны по три целых числа $$$a_i$$$, $$$b_i$$$ и $$$s_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$1 \le s_i \le 10^9$$$) — начальный и конечный город, а также стоимость $$$i$$$-го авиарейса.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$800$$$, а также, что сумма $$$m$$$ по всем наборам входных данных не превосходит $$$10000$$$.

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

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

Пример

Входные данные
4
4 4 2
7 4 3 1
1 2 21
3 2 6
1 3 8
2 4 11
4 4 10
1 2 10 1
1 2 20
2 4 30
1 3 25
3 4 89
4 4 7
5 1 6 2
1 2 5
2 3 10
3 4 50
3 4 70
4 1 2
1 1 1 1
1 3 2
Выходные данные
4
24
10
-1
Примечание

В первом примере Боре оптимально сделать $$$4$$$ представления в первом городе, имея в итоге $$$2 + 7 \cdot 4 = 30$$$ рублей, а потом пройтись по маршруту $$$1-3-2-4$$$, потратив $$$6+8+11=25$$$ рублей.

Во втором примере Боре оптимально сделать $$$15$$$ представлений в первом городе, полететь в $$$3$$$ город, сделать там $$$9$$$ представлений, и далее отправиться в $$$4$$$ город.