Way Home

The famous magician Borya Budini was traveling through a country X made up of $n$ cities. Unfortunately, he was robbed in city 1. Now he has a long road ahead to get home to city $n$.

He travels by plane. The country has $m$ flights. The $i$-th flight goes from $a_i$ to $b_i$ and costs $s_i$. To take a flight, Borya must be in city $a_i$ and have at least $s_i$ money on hand, which he spends on the flight.

After the robbery he has only $p$ rubles left. He does not give up, though. While in city $i$, he can give a performance every day, and each performance earns him $w_i$ rubles.

Help the magician find out whether he can get home, and if so, the minimum number of performances he must give to do it.

The first line contains four integers $n$, $m$, $p$, and $g$ ($2 \le n \le 800$, $1 \le m \le 3000$, $0 \le p \le 10^9$, $0 \le g \le 6$): the number of cities, the number of flights, the initial money, and the test group number.

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($1 \le w_i \le 10^9$), the profit from one performance in each city.

Each of the next $m$ lines contains three integers $a_i$, $b_i$, and $s_i$ ($1 \le a_i, b_i \le n$, $1 \le s_i \le 10^9$): the departure city, the destination city, and the price of the $i$-th flight.

Print a single integer: the minimum number of performances Borya must give to get home, or $-1$ if it is impossible.

In the first example, the best plan is to give 4 performances in city 1, which leaves Borya with $2 + 7 \cdot 4 = 30$ rubles. He then flies the route $1-3-2-4$, spending $6+8+11=25$ rubles.

In the second example, the best plan is to give 15 performances in city 1, fly to city 3, give 9 performances there, and then fly on to city 4.