19208번 - Aarelia Mountains 다국어

You are a powerful wizard travelling across the Aarelia kingdom. Your path lies across the land of steep hills and mountains. The mountain area can be represented as a row of $n$ regions; each region has its elevation $h_i$. 

Unfortunately, you have no climbing equipment (and, frankly, no climbing skills), and your Flight spells are exhausted. However, you will be able to travel across the area when region elevations will form a non-decreasing sequence, that is, $h_i \leq h_{i+1}$ for each $i$ from 1 to $(n-1)$ (you are travelling from right to left, and high falls are no threat for you).

The only spell that can help you is the Earthquake spell. The spell affects several adjacent regions and allows you to alter their elevation. You know $m$ varieties of the Earthquake spell; each spell has its range $l_i$ (that is, number of adjacent regions affected by the spell), its energy cost $c_i$ and can either raise or lower all affected regions' elevation by 1 (a single spell can be applied either to raise or lower regions, but not both). Each spell can be applied to any range of length $l_i$ that lies completely within the area, and can be cast an unlimited number of times (paying energy cost after each repetition). It is possible that some of the regions will have negative elevation after casting a spell.

Determine whether it is possible to alter the landscape so that you may travel safely across the area, and if it is, find the lowest total energy you have to spend on casting the spells.

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

The second line contains $n$ space-separated integers $h_i$ --- initial elevation of the regions ($0 \leq h_i \leq 10^6$).

The next $m$ lines describe varieties of the Earthquake spell you know. The $i$-th of these lines describes the spell variety according to format ``$t_i$ $l_i$ $c_i$''; here $t_i$ is the character "+" if the spell allows to raise elevations by 1, or "-" if it allows to lower elevations by 1; $l_i$ and $c_i$ are the range and the energy cost of the spell, respectively ($1 \leq l_i \leq n$, $1 \leq c_i \leq 10^6$).

It it is possible to travel across the area, print the lowest total energy that must be spent on casting the spells, otherwise print $-1$.