Путь домой

문제

Известный фокусник Боря Будини путешествовал по стране $XX$, которая состоит из $nn$ городов. Однако случилось несчастье, и его обокрали в городе номер $11$. Теперь Будини предстоит нелегкий путь домой в город $nn$.

Добираться он собирается самолетами. Всего в стране есть $mm$ авиарейсов, $ii$-й летит из $a_{i}a\_i$ в $b_{i}b\_i$ и стоит $s_{i}s\_i$. Чтобы им воспользоваться, Боря должен быть в городе $a_{i}a\_i$ и иметь на руках хотя бы $s_{i}s\_i$ денег (которые он потратит на перелет).

После ограбления у него осталось всего $pp$ рублей, однако он не отчаивается! Находясь в городе $ii$, он может хоть каждый день организовывать представления, которые будут приносить ему по $w_{i}w\_i$ рублей.

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

입력

Первая строка содержит четыре целых числа $nn$, $mm$, $pp$ и $gg$ ($2\le n\le 8002\; \backslash le\; n\; \backslash le\; 800$, $1\le m\le 30001\; \backslash le\; m\; \backslash le\; 3000$, $0\le p\le {10}^{9}0\; \backslash le\; p\; \backslash le\; 10^9$, $0\le g\le 60\; \backslash le\; g\; \backslash le\; 6$) --- количество городов, количество авиарейсов, изначальное количество рублей и номер группы тестов.

Во второй строке даны $nn$ целых чисел $w_1,w_2,\dots ,w_{n}w\_1,\; w\_2,\; \backslash ldots,\; w\_n$ $(1\le w_i\le {10}^9)(1\; \backslash le\; w\_i\; \backslash le\; 10^9)$ --- прибыль от представлений.

В следующих $mm$ строках даны по три целых числа $a_{i}a\_i$, $b_{i}b\_i$ и $s_{i}s\_i$ ($1\le a_i,b_i\le n1\; \backslash le\; a\_i,\; b\_i\; \backslash le\; n$, $1\le s_i\le {10}^{9}1\; \backslash le\; s\_i\; \backslash le\; 10^9$) --- начальный и конечный город, а также стоимость $ii$-го авиарейса.

출력

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

힌트

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

Во втором примере Боре оптимально сделать $1515$ представлений в первом городе, полететь в $33$ город, сделать там $99$ представлений, и далее отправиться в $44$ город.

4 4 2 0
7 4 3 1
1 2 21
3 2 6
1 3 8
2 4 11

4

4 4 10 0
1 2 10 1
1 2 20
2 4 30
1 3 25
3 4 89

24

4 4 7 0
5 1 6 2
1 2 5
2 3 10
3 4 50
3 4 70

10

4 1 2 0
1 1 1 1
1 3 2

-1