The latest craze in personal transportation is jetstream riding, in which a rider flies through a tunnel of wind located just above the stratosphere in order to get from point A to B. As a casual employee of just over nine thousand small businesses around the globe, Lillian has taken to jetstream riding for its speed and convenience. It's even faster than taking the m9!
Lillian can ride on N different jetstreams, each D kilometres long, arranged side-by-side, parallel to each other and all flowing in the same direction. These jetstreams are labelled left-to-right with integers from 1 to N. Jetstream i allows Lillian to travel a kilometre in vi seconds. She begins at the start of jetstream S and needs to reach the end of jetstream E.
While it is possible to jump between adjacent jetstreams instantaneously, there are C clouds of toxic ozone gas lingering between adjacent pairs of jetstreams. Due to strict government regulations (and the fact that Lillian wishes to survive her journey without contracting acute bronchitis), these ozone clouds cannot be crossed, even at their endpoints.
Your task is to determine the fastest possible time that Lillian can complete her journey in.
The first line of input will contain five integers: N, C, D, S and E, all separated by spaces.
The following N lines each contain a single integer vi, representing the number of seconds it takes to travel a kilometre in the ith jetstream.
The following C lines each contain three integers: lc, bc and fc, representing the index of the jetstream immediately left of the cth ozone cloud, the distance (in kilometres) of the starting point of the cloud from the beginning of the jetstreams and the distance of the ending point of the cloud from the beginning of the jetstreams respectively. It is guaranteed that these ozone clouds will not intersect or touch at endpoints.
Output should consist of one line containing one integer: the fastest possible time it takes Lillian to complete her journey (in seconds). You are guaranteed that it is always possible to reach the end of jetstream E from the start of jetstream S.
3 2 3 1 3 100 10 1 1 0 1 2 1 2
3 2 3 3 1 1 10 100 1 0 1 2 1 2
4 6 7 1 1 10 5 2 1 2 5 7 1 2 4 3 4 7 2 0 1 1 6 7 2 2 3
For sample case 1, Lillian starts in jetstream 1 and has to end in jetstream 3 after covering 3km. She must ride jetstream 1 for 1km since there is a cloud blocking her way to jetstream 2. This takes 100 seconds. Instantly after the first kilometre Lillian can transfer to jetstream 2, this takes no extra time in jetstream 1 so she covers the second kilometre in 10 seconds. Similarly just after the end of kilometre two Lillian transfers into jetstream 3 where she rides out the final kilometre in 1 second. Thus the whole trip takes 111 seconds.
For sample case 2, Lillian can immediately transfer from jetstream 3 to jetstream 2 where she travels the first kilometre in 10 seconds. Once the ozone cloud blocking lane 1 is passed, Lillian transfers into jetstream 1. She stays there for the next 2km, which takes 2 seconds and so 12 seconds overall.
For sample case 3, Lillian immediately transfers from jetstream 1 to 2 and rides that for 1km, taking 5 seconds. Directly after the ozone cloud blocking her finishes Lillian jumps over to jetstream 4 and rides it for 3km, which takes her 3 seconds. Then she transfers to jetstream 3 just before the next ozone cloud would block her and stays there for 1km, taking 2 seconds. Similarly just before each of the next two ozone clouds start Lillian transfers past them. Thus she spends 5 seconds in jetstream 2, and then 10 in jetstream 1. Thus her journey is 25 seconds.
For all subtasks: 1 ≤ N ≤ 100,000, 0 ≤ C ≤ 100,000, 1 ≤ D ≤ 1,000,000,000, 1 ≤ vi ≤ 100,000, 2 ≤ lc < N, 0 ≤ bc < fc ≤ D.