AUTOCESTA

문제

One well known wealthy trader has figured out a way to save on road tolls which his trucks pay on the state highway. Simply put - he will buy the highway. After some thinking, he came up with an even better plan - he will only buy those parts of the highway which are most profitable. That way the trucks whose routes are completely owned by him won't have to pay any toll. 

The highway is split into sections with length of one kilometer. For each kilometer of the highway we know its purchase price. 

To determine which sections he wants to buy, the trader will check out the ride plan for the next year. He knows all the routes his trucks will ride. Each route is determined with three numbers A, B and C in the following manner: 

• On that route the truck will enter the highway A kilometers from the start of the highway and leave the highway B kilometers from the start, thus traveling |B-A| kilometers on the highway. For instance, if the truck needs to drive L kilometers from the start of the highway, A=0 and B=L. 
• If the whole route from A to B is owned by the trader, the truck won't pay any toll. Otherwise, if the truck has to pass through at least one section not owned by the trader, he will have to pay total of C (regardless of the number of state owned sections of the highway that the truck has to pass through). 

Additionally, the state has set a simple law - on each section of the highway, at most K trucks can pass in one direction and K in the other direction. However, this law only holds for the sections of the highway owned by the state (i.e. not owned by the trader). 

Write a program that calculates he minimal total expense for the wealthy trader, in such a way that all his trucks can take complete their routes. The total expense is defined as the expense for buying some parts of the highway plus all the tolls paid by every truck going by a route not owned by the trader. 

입력

In the first line you can read L (1 ≤ L ≤ 100 000), total length of the highway in kilometers. 

In the second line there are L integers X_i (0 ≤ X_i ≤ 1 000 000 000), purchase price of i-th section of the highway. 

Third line contains N (1 ≤ N ≤ 100 000), the number of routes the trucks will take. 

In each of the following N lines there are three integers A_i, B_i and C_i (0 ≤ A_i, B_i ≤ L, A_i ≠ B_i, 0 ≤ C_i ≤ 1 000 000 000), description of i-th route. 

Last line contains number K (1 ≤ K ≤ 100), maximal number of trucks that can go in each direction on a state owned section of the highway.

출력

Write only one integer - minimal total expense for the trader if he optimally selects and buys some sections of the highway.

힌트

If the trader doesn't buy any section, he must pay a total of 800 - 400 of toll for each route. If he buys the whole highway, he will pay 900. But if he buys only second section, he will pay 300 for it plus 400 for toll for first route (second route goes only through second section). 

3
300 300 300
2
0 3 400
2 1 400
99

700

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

15