직원 고용

BuBu는 올림픽 유치에 성공한 뒤, 올림픽 위원회 자회사의 인사부장 자리에 올랐다. 첫 출근 날, 그는 어려운 문제에 부딪혔다. 새 올림픽 사업에 쓸 단기 직원을 모집해야 한다. 대략 추정하면 이 사업은 $N$일이 걸리고, $i$일째에는 최소 $A_i$명의 직원이 필요하다.

고용할 수 있는 직원 유형은 총 $M$가지다. 유형 $i$ 직원은 $S_i$일부터 $T_i$일까지 일하며, 1명당 $C_i$달러를 지급해야 한다. BuBu는 매일 필요한 인원을 채우면서 총비용을 가장 낮추려 한다. 최적의 고용 계획을 찾도록 도와 달라. 각 유형의 직원 수에는 제한이 없다.

첫 줄에 정수 $N$과 $M$이 주어진다.

둘째 줄에 $N$개의 음이 아닌 정수 $A_1, A_2, \ldots, A_N$이 주어진다.

이어지는 $M$개의 줄에는 각각 직원 유형 하나를 나타내는 정수 $S_i$, $T_i$, $C_i$가 한 줄에 하나씩 주어진다.

최적의 고용 계획에 드는 비용을 나타내는 정수 하나를 한 줄에 출력한다.

$1 \le N \le 1000$

$1 \le M \le 10000$

입력의 나머지 값은 모두 $2^{31} - 1$을 넘지 않는다.