Minimum Cost Tower Defense

Consider a line of n locations (indexed 1 through n). At location i building one tower costs \(C_i\) and you may build as many towers as you wish at that position (the cost is linear). There are m intervals given as \([L_1,R_1], [L_2,R_2], \dots, [L_m,R_m]\). In the i-th interval you must have built at least \(D_i\) towers in total (i.e. the sum of towers built at positions between \(L_i\) and \(R_i\)). Your task is to choose how many towers to build at each location so that all interval requirements are met and the total cost \(\sum_{i=1}^{n} C_i\,x_i\) is minimized. This can be formulated as:

[ \text{Minimize } \sum_{i=1}^{n} C_i,x_i \quad \text{subject to} \quad \sum_{i=L}^{R} x_i \ge D \quad \text{for each interval } [L,R]. ]

Note: Since the constraint matrix (with consecutive ones) is totally unimodular, an optimal integer solution exists. One way to solve this problem (for small constraints) is to use a greedy strategy: process the intervals in increasing order of their right endpoint; for each interval, if the current total towers built in that interval is less than \(D\), add the extra (shortage) towers at the position in the interval with the smallest cost \(C_i\). This greedy algorithm yields the optimal answer in this setting.

inputFormat

The first line contains two integers n and m (the number of positions and the number of intervals). The second line contains n integers \(C_1, C_2, \dots, C_n\) where \(C_i\) is the cost to build one tower at position i. Each of the next m lines contains three integers \(L\), \(R\) and \(D\) indicating that in the interval from position \(L\) to R (inclusive) you must have built at least \(D\) towers.

outputFormat

Output a single integer: the minimum total cost required to satisfy all the interval requirements.

sample

5 2
3 1 2 6 4
1 3 2
2 5 3

3