Fuel Problem

Time Limit : 8 sec, Memory Limit : 131072 KB

Problem G: Fuel Problem

Today, Mr. Fisher is going to a town from his hometown by car. As his schedule is not so tight, he is planning to trade fuel in towns on his way to gain some money.

At the beginning, the tank of the car is filled up. Mr. Fisher can buy or sell any amount of fuel at any town, including the hometown and the destination, but he needs one unit of fuel to drive one unit of distance. Also, he cannot hold fuel more than the capacity of the tank of his car. Even though he is not in a hurry, he would not like to buy or sell so many times, namely, more than Q times. The price of fuel varies in each town.

He would like to maximize the gain from the trade under these conditions. He calls you, an excellent programmer, for a help.

Your task is to calculate the maximum gain. Here, the gain means the increase in the amount of money at the end of the drive from the beginning. The amount of the fuel at the end is not taken into the account. You can assume that Mr. Fisher has enough money at the beginning; it is acceptable for him to lose some money on the way or even at the end. If he has to lose some money to reach the destination, minimize the loss.


The input is given in the following format:

R1 R2 ... RN
A1 B1 D1
A2 B2 D2
. . .

The first line contains two integers N and M (2 ≤ N ≤ 300). N indicates the number of towns and M indicates the number of roads. The second line contains four integers S, T, F and Q (1 ≤ S, TN, 0 < F ≤ 10000, 0 < Q ≤ 100). S and T indicates the hometown and the destination town respectively; F indicates the capacity of the tank; and Q indicates the maximum number of times he is going to buy or sell the fuel. The third line contains N integers Ri (0 ≤ Ri ≤ 1000). Ri indicates the rate of fuel (the price for one unit of fuel) in the i-th town. The following M lines describe the roads between the towns. The j-th line contains three integers Aj, Bj and Dj (1 ≤ Aj, Bj ≤ N, 0 < Dj ≤ 1000), which denotes there is a bidirectional road between Aj-th and Bj-th towns and the distance is Dj.


Output a line containing the maximum gain. If he must lose money, output the minimum loss with a minus sign. In case he cannot arrive the destination in any way, output "impossible" instead.

Sample Input 1

5 5
1 5 5 5
0 4 2 3 10
1 2 5
2 3 1
2 4 5
3 4 2
4 5 3

Output for the Sample Input 1


Sample Input 2

2 1
1 2 20 10
0 10
1 2 5

Output for the Sample Input 2


Sample Input 3

3 3
1 2 10 3
0 0 5
1 2 5
2 3 4
1 3 3

Output for the Sample Input 3


Sample Input 4

3 2
1 3 10 1
5 5 5
1 2 10
2 3 10

Output for the Sample Input 4


Source: ACM-ICPC Japan Alumni Group Winter Camp , Day 2, Tokyo, Japan, 2009-02-22