Задача №115257. Путь домой
Известный фокусник Боря Будини путешествовал по стране \(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\) город.
Тесты к этой задаче состоят из 6 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | |||||||
| Группа | Баллы | \(n\) | \(m\) | \(s_i\) | \(w_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | – | Тесты из условия. |
| 1 | 14 | – | – | – | \(w_i=1\) | – | |
| 2 | 13 | – | \(m = n - 1\) | – | – | – | \(a_i = i\), \(b_i = i + 1\) |
| 3 | 17 | \(n \le 10 \) | – | – | – | 0 | |
| 4 | 19 | \(n \le 100 \) | – | \(s_i \le 100\) | – | 0 | |
| 5 | 21 | \(n \le 100 \) | – | – | – | 0, 3, 4 | |
| 6 | 16 | – | – | – | – | 0 – 5 | Offline-проверка. |
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