Highway Purchase Optimization

You are given a highway of length \(L\) kilometers divided into 1‐kilometer segments (segments numbered 1 through \(L\)). Each segment \(i\) can be purchased at a cost \(X_i\) (in dollars). Initially, none of the highway is purchased.

There are \(n\) trucks. Each truck \(j\) is described by three integers \(A_j, B_j, C_j\). Truck \(j\) enters the highway at kilometer \(A_j\) and exits at kilometer \(B_j\). Its route covers all segments with indices from \(s_j = \min(A_j, B_j) + 1\) to \(e_j = \max(A_j, B_j)\) (both inclusive). Moreover, the truck travels in the positive direction if \(A_j B_j\).

If a truck passes through any segment that is not purchased, you must pay a penalty cost of \(C_j\) for that truck (regardless of the number of non‐purchased segments on its route). However, if every segment on its route is purchased, no penalty is incurred for that truck.

There is one more twist. For each segment that is not purchased, there is a capacity constraint: in each direction (positive and negative) at most \(K\) trucks are allowed to pass using that segment. In other words, for an unpurchased segment \(i\), if you count the penalty trucks (i.e. trucks which did not have their entire route purchased) that travel through segment \(i\) in the positive direction and separately those that travel in the negative direction, each count must not exceed \(K\).

Your goal is to decide which segments to purchase (and thereby possibly “upgrade” some trucks so that they do not pay a penalty) such that the total cost – the sum of the purchase cost for the segments you buy plus the penalty cost for every truck whose route is not completely purchased – is minimized. It is guaranteed that purchasing all segments is always a feasible (but not necessarily optimal) solution.

Input/Output Formats

inputFormat

The first line contains three integers \(L, n,\) and \(K\) (\(1 \le L \le 15\), \(1 \le n \le 15\); note that the bounds are small to allow exhaustive search).

The second line contains \(L\) integers \(X_1, X_2, \ldots, X_L\) representing the purchase cost for each kilometer.

Then \(n\) lines follow. Each of these lines contains three integers \(A, B, C\) describing a truck’s route and penalty cost, where the truck enters the highway at kilometer \(A\) and exits at kilometer \(B\) (with \(A \neq B\)).

outputFormat

Output a single integer, the minimum total cost.

sample

5 2 1
3 2 1 4 5
0 3 10
2 5 8

14