(mathcal{Description})
Link.
一项持续 (n) 天的任务，第 (i) 天需要至少 (a_i) 人工作。还有 (m) 种雇佣方式，第 (i) 种每雇佣一人代价为 (c_i)，此人会从第 (s_i) 天工作到第 (t_i) 天（包括边界）。求满足条件的最小代价和。
(nle10^3)，(mle10^4)。
(mathcal{Solution})
非常巧妙地题意转化。
初始时刻，有 (+infty) 人待业，限制第 (i) 天至多 (+infty-a_i) 人待业（那么至少就有 (a_i) 人上工）。雇佣一个人相当于用 (c_i) 的费用让一个人从 (s_i) 天起上工，到 (t_i+1) 天恢复待业状态。所以最小费用最大流建图为：
- (i ightarrow i+1)，流量 (+infty-a_i)，费用为 (0)；
- (s_i ightarrow t_i+1)（建一个虚点 (T=n+1)），流量 (+infty)，费用 (c_i)。
跑最小费用最大流即可。复杂度 (mathcal O(operatorname{Dinic}(n,n+m)))。
(mathcal{Code})
/* Clearink */
#include <queue>
#include <cstdio>
typedef long long LL;
typedef std::pair<LL, LL> PLL;
const int MAXN = 1e3, MAXM = 1e4;
const LL INF = 1ll << 60;
int n, m;
inline LL imin ( const LL a, const LL b ) { return a < b ? a : b; }
// 这个 MFCG 其实是错的，SPFA d[i] 应初始化为 INF 而非 -1.
struct MaxFlowCostGraph {
static const int MAXND = MAXN + 2, MAXEG = MAXN + MAXM + 1;
int ecnt, head[MAXND + 5], S, T, bound, curh[MAXND + 5];
LL d[MAXND + 5];
bool inq[MAXND + 5];
struct Edge { int to; LL flw; int cst, nxt; } graph[MAXEG * 2 + 5];
MaxFlowCostGraph (): ecnt ( 1 ) {}
inline void link ( const int s, const int t, const LL f, const int w ) {
graph[++ecnt] = { t, f, w, head[s] };
head[s] = ecnt;
}
inline Edge& operator [] ( const int k ) { return graph[k]; }
inline void operator () ( const int s, const int t, const LL f, const int w ) {
#ifdef RYBY
printf ( "%d %d ", s, t );
if ( f == INF ) printf ( "INF " );
else printf ( "%lld ", f );
printf ( "%d
", w );
#endif
link ( s, t, f, w ), link ( t, s, 0, -w );
}
inline bool spfa () {
static std::queue<int> que;
for ( int i = 0; i <= bound; ++i ) d[i] = -1, inq[i] = false;
d[S] = 0, inq[S] = true, que.push ( S );
while ( !que.empty () ) {
int u = que.front (); que.pop ();
inq[u] = false;
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( graph[i].flw
&& ( !~d[v = graph[i].to] || d[v] > d[u] + graph[i].cst ) ) {
d[v] = d[u] + graph[i].cst;
if ( !inq[v] ) que.push ( v ), inq[v] = true;
}
}
}
return ~d[T];
}
inline PLL dfs ( const int u, const LL iflw ) {
if ( u == T ) return { iflw, 0 };
inq[u] = true; PLL ret ( 0, 0 );
for ( int& i = curh[u], v; i; i = graph[i].nxt ) {
if ( graph[i].flw && !inq[v = graph[i].to]
&& d[v] == d[u] + graph[i].cst ) {
PLL oflw ( dfs ( v, imin ( iflw - ret.first, graph[i].flw ) ) );
graph[i].flw -= oflw.first, graph[i ^ 1].flw += oflw.first;
ret.first += oflw.first;
ret.second += graph[i].cst * oflw.first + oflw.second;
if ( ret.first == iflw ) break;
}
}
if ( !ret.first ) d[u] = -1;
return inq[u] = false, ret;
}
inline PLL calc ( const int s, const int t ) {
S = s, T = t;
PLL ret ( 0, 0 );
while ( spfa () ) {
for ( int i = 0; i <= bound; ++i ) inq[i] = false, curh[i] = head[i];
PLL tmp ( dfs ( S, INF ) );
ret.first += tmp.first, ret.second += tmp.second;
}
return ret;
}
} graph;
int main () {
scanf ( "%d %d", &n, &m );
int S = 0, T = graph.bound = n + 1;
graph ( S, 1, INF, 0 );
for ( int i = 1, a; i <= n; ++i ) {
scanf ( "%d", &a );
graph ( i, i + 1, INF - a, 0 );
}
for ( int i = 1, s, t, c; i <= m; ++i ) {
scanf ( "%d %d %d", &s, &t, &c );
graph ( s, t + 1, INF, c );
}
printf ( "%lld
", graph.calc ( S, T ).second );
return 0;
}