Aarelia 산맥

당신은 Aarelia 왕국을 여행하는 강력한 마법사이다. 여행 경로는 가파른 언덕과 산이 많은 지역을 지난다. 산악 지역은 한 줄로 늘어선 $n$개의 구역이며, 구역 $i$의 고도는 $h_i$이다.

등반 장비는 없고(솔직히 등반 기술도 없다), 비행 주문도 이미 모두 소진되었다. 구역들의 고도가 비감소 수열을 이룰 때, 즉 1부터 $(n-1)$까지의 모든 $i$에 대해 $h_i \leq h_{i+1}$일 때에만 이 지역을 지날 수 있다. 오른쪽에서 왼쪽으로 이동하므로, 높은 낭떠러지는 문제가 되지 않는다.

지나가는 데 도움이 되는 주문은 지진 주문뿐이다. 지진 주문은 인접한 여러 구역에 작용해 그 고도를 바꾼다. 알려진 지진 주문은 $m$종류이다. 종류 $i$는 영향을 받는 인접 구역의 수 $l_i$와 시전 비용 $c_i$를 가지며, 영향을 받는 모든 구역의 고도를 1 올리거나 1 내린다. 한 종류를 올리는 데와 내리는 데 동시에 쓸 수는 없다. 전체 지역 안에 완전히 들어가는 길이 $l_i$의 구간이라면 어디에든 적용할 수 있고, 횟수 제한 없이 시전할 수 있지만 시전할 때마다 비용을 낸다. 시전 후 고도가 음수가 되는 구역이 있어도 된다.

지형을 바꿔 안전하게 지날 수 있는지 판단하라. 지날 수 있다면 주문 시전에 드는 최소 합계 에너지를 구하라.

첫째 줄에 두 정수 $n$과 $m$이 주어진다 ($1 \leq n, m \leq 200$).

둘째 줄에는 각 구역의 초기 고도인 정수 $n$개 $h_i$가 주어진다 ($0 \leq h_i \leq 10^6$).

다음 $m$개 줄은 지진 주문의 종류를 나타낸다. $i$번째 줄은 t_i l_i c_i 형식이며, t_i는 고도를 1 올리는 주문이면 +, 1 내리는 주문이면 -이다. $l_i$는 범위이고 $c_i$는 시전 비용이다 ($1 \leq l_i \leq n$, $1 \leq c_i \leq 10^6$).

지날 수 있다면 주문 시전에 필요한 최소 합계 에너지를 출력한다. 지날 수 없다면 -1을 출력한다.