The famous magician Borya Budini was traveling through country X, which consists of $n$ cities. However, a misfortune occurred, and he was robbed in city number 1. Now, Budini faces a difficult journey home to city $n$.

He intends to travel by plane. There are $m$ flights in the country in total; the $i$-th flight goes from $a_i$ to $b_i$ and costs $s_i$. To use it, Borya must be in city $a_i$ and have at least $s_i$ money on hand (which he will spend on the flight).

After the robbery, he has only $p$ rubles left, but he does not despair! While in city $i$, he can organize performances every day, which will bring him $w_i$ rubles each.

Help the magician find out if he can get home, and what is the minimum number of performances he will have to organize to do so.

Input

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 amount of rubles, and the test group number.

The second line contains $n$ integers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 10^9$) — the profit from performances.

The next $m$ lines each contain 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 starting city, the destination city, and the cost of the $i$-th flight.

Output

Output a single integer — the minimum number of performances Borya will have to organize to get home, or $-1$ if it is impossible.

Examples

Input 1

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

Output 1

4

Input 2

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

Output 2

24

Input 3

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

Output 3

10

Input 4

4 1 2 0
1 1 1 1
1 3 2

Output 4

-1

Note

In the first example, it is optimal for Borya to perform 4 times in the first city, having a total of $2 + 7 \cdot 4 = 30$ rubles, and then follow the route $1 - 3 - 2 - 4$, spending $6 + 8 + 11 = 25$ rubles.

In the second example, it is optimal for Borya to perform 15 times in the first city, fly to the 3rd city, perform 9 times there, and then head to the 4th city.

Subtasks

The tests for this problem consist of 6 groups. Points for each group are awarded only if all tests in the group and all tests of some previous groups are passed. Note that passing the example tests is not required for some groups. "Offline-check" means that the results of testing your solution on this group will only be available after the competition ends.