The Fuel#45
boiler rooms of equal capacity are connected by pipes, forming a pipeline system for transferring fuel. At 9\!:\!00 a.m., it is discovered that the actual fuel reserve in each boiler room is A_k tons (k = 1 \ldots N), with one of the rooms having tons less than the norm, and all remaining rooms containing at least the norm or more.
The total fuel supply is sufficient to restore the proper reserves by redistribution. At any moment, out of pumps, either or can operate at the same time (they must be located in neighboring boiler rooms — one sending, one receiving). Transferring ton of fuel over km takes minutes.
Determine the minimal time (in minutes) required to complete the redistribution.
The first line contains four integers: N, M, B, C — the number of boiler rooms, the number of pipes, the fuel deficit in one room, and the time (in minutes) to transport ton of fuel over km, respectively.
The second line contains the array A_1, \ldots, A_N — the fuel reserves (in tons) in each boiler room.
Each of the following lines contains three integers: the indices of two boiler rooms (connected by a pipe) and the length (in kilometers) of this pipe.
All values are non-negative integers not exceeding .
Print a single integer — the minimal required time.
Example 10