Buying a Highway

Sanggeun runs a trucking company and wants to reduce next year's tolls by buying some highway segments.

The highway is divided into L segments, each 1 km long, and each segment has its own purchase cost. A truck pays no toll if every segment on its route is owned by Sanggeun. If at least one segment on the route is not owned by him, the truck pays its fixed toll C exactly once. The toll does not depend on how many segments the truck travels.

For each truck scheduled for next year, Sanggeun knows its route. A route is described by three integers A, B, and C. The truck enters the highway at the point A km from the beginning and exits at the point B km from the beginning, so it travels through |B-A| one-kilometer segments.

The country also has a simple traffic law: on every segment, at most K vehicles may travel in the same direction. The opposite direction is counted separately and also allows at most K vehicles. This restriction does not apply to segments owned by Sanggeun.

Find the minimum possible total cost, where the total cost is the sum of purchased segment costs and tolls paid by the trucks.

The first line contains the total highway length L. (1 <= L <= 100,000)

The second line contains L integers X_i. X_i is the cost of buying the i-th one-kilometer segment. (0 <= X_i <= 1,000,000,000)

The third line contains the number of trucks N. (1 <= N <= 100,000)

Each of the next N lines contains three integers A_i, B_i, and C_i, describing one truck. The truck enters at A_i km and exits at B_i km. (0 <= A_i, B_i <= L, A_i != B_i, 0 <= C_i <= 1,000,000,000)

The last line contains K. (1 <= K <= 100)

Print the minimum cost of operating the company next year.