Aarelia Mountains

You are a powerful wizard travelling across the Aarelia kingdom. Your path lies across a land of steep hills and mountains. The mountain area is a row of $n$ regions, and region $i$ has elevation $h_i$.

You have no climbing equipment (and, frankly, no climbing skills), and your Flight spells are used up. You can cross the area only when the elevations form a non-decreasing sequence, that is, $h_i \leq h_{i+1}$ for each $i$ from 1 to $(n-1)$. You travel from right to left, so high falls are no threat.

The only spell that can help is the Earthquake spell. Each Earthquake spell affects several adjacent regions and changes their elevation. You know $m$ varieties of the spell. Variety $i$ has a range $l_i$ (the number of adjacent regions it affects) and an energy cost $c_i$, and it either raises or lowers all affected regions by 1. A variety cannot both raise and lower. It can be applied to any range of length $l_i$ that lies completely within the area, and you may cast it an unlimited number of times, paying the energy cost after each cast. Some regions may end up with negative elevation.

Determine whether you can alter the landscape so that you can travel safely, and if so, find the lowest total energy you must spend on casting spells.

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 200$).

The second line contains $n$ integers $h_i$ ($0 \leq h_i \leq 10^6$), the initial elevations of the regions.

The next $m$ lines describe the varieties of the Earthquake spell. Line $i$ has the form t_i l_i c_i, where t_i is + if the spell raises elevations by 1, or - if it lowers them by 1. Here $1 \leq l_i \leq n$ and $1 \leq c_i \leq 10^6$.

If travel is possible, print the lowest total energy that must be spent on casting spells. Otherwise, print -1.