Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem J: Business Lady

Problem J: Business Lady

Time Limit: 5 Sec  Memory Limit: 32 MB
Submit: 4  Solved: 1
[Submit][Status][Web Board]


Today, Biving is going to a town from her hometown by car. As her schedule is not so tight, she is planning to trade fuel in towns on her way to gain some money.

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

She would like to maximize the gain from the trade under these conditions. She 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 Biving has enough money at the beginning; it is acceptable for her to lose some money on the way or even at the end. If she has to lose some money to reach the destination, minimize the loss.


The input contains multiple test cases (<= 30).

Each test case 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, T N, 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 she 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.



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


Sample Input

2 1
1 2 20 10
0 10
1 2 5
2 0
1 2 20 10
0 10
3 2
1 3 10 1
5 5 5
1 2 10
2 3 10

Sample Output



[Submit][Status][Web Board]