Известный фокусник Боря Будини путешествовал по стране
\(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\) монет каждый.
Помогите фокуснику узнать, сможет ли он добраться до дома, а также какое минимальное количество представлений придется для этого организовать.
Выходные данные
Для каждого теста выведите единственное целое число — минимальное количество представлений, которое придется организовать Боре, чтобы добраться до дома, или \(-1\), если это сделать невозможно.
Примечание
В первом примере Боре оптимально сделать \(4\) представления в первом городе, имея в итоге \(2 + 7 \cdot 4 = 30\) рублей, а потом пройтись по маршруту \(1-3-2-4\), потратив \(6+8+11=25\) рублей.
Во втором примере Боре оптимально сделать \(15\) представлений в первом городе, полететь в \(3\) город, сделать там \(9\) представлений, и далее отправиться в \(4\) город.
Примеры
| № | Входные данные | Выходные данные |
|
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
|