30639번 - Путь домой 서브태스크다국어

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

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

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

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

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

Во второй строке даны $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$-го авиарейса.

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

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

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