Maximizing Net Profit on a Performance Street

ID: 21052

Type: Default

1000ms

256MiB

WuuTue is planning a series of performances on a straight east‐west street in city T. The street has $n$ stages numbered from $1$ to $n$ (from west to east). There are $M$ proposed performances; the $i$ –th performance can be held on all consecutive stages from $l_i$ to $r_i$ (inclusive) and will yield a revenue of $v_i$ dollars if held. However, the stages are originally built for human performances. In order to allow animal performances, each stage must be strengthened at a cost. Strengthening stage $j$ costs $c_j$ dollars and each stage only needs to be strengthened once, even if it is used for multiple performances.

WuuTue may choose to cancel any performance if its revenue does not cover the strengthening costs. When a set $S$ of performances is chosen, the net profit is computed as

Profit = \sum_{i\in S} v_i - \sum_{j \in U} c_j,

where the union set of stages

U = \bigcup_{i\in S} \{l_i,l_i+1,\dots,r_i\}

is strengthened (each stage cost is counted only once).

Your task is to help WuuTue choose a subset of performances (possibly cancelling some) so that the net profit is maximized. Note that it is allowed that the performances in $S$ overlap. If no performance yields a positive net profit, you may choose to cancel all performances (resulting in a net profit of $0$ ).

inputFormat

The first line contains two integers $n$ and $M$ --- the number of stages and the number of proposed performances.
The second line contains $n$ integers $c_1, c_2,\dots,c_n$ , where $c_j$ is the cost to strengthen stage $j$ .
Each of the following $M$ lines contains three integers $l_i$ , $r_i$ , and $v_i$ , indicating that the $i$ –th performance requires consecutive stages from $l_i$ to $r_i$ and will bring a revenue of $v_i$ dollars.

outputFormat

Output a single integer --- the maximum net profit achievable.

sample

#P7867. Maximizing Net Profit on a Performance Street

Maximizing Net Profit on a Performance Street