Magic Mountain Manipulation

In this problem, you are given n mountains with initial heights \(h_1, h_2, \ldots, h_n\). You also have m types of magic spells. Each spell of type \(i\) is characterized by two integers: \(l_i\) and \(c_i\). When you cast a spell of type \(i\) on any contiguous segment of exactly \(l_i\) mountains, you can either raise or lower the height of every mountain in that segment by 1. Each such use of the spell costs \(c_i\) points of energy. At every moment the height of any mountain must remain nonnegative.

Your task is to determine the minimum total energy cost required so that after some sequence of spell casts the final heights of the mountains are non‐decreasing (i.e. \(H_1 \le H_2 \le \cdots \le H_n\), where \(H_i = h_i + f(i)\) and \(f(i)\) is the net adjustment made on mountain \(i\)).

All formulas in this statement are given in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(m\) -- the number of mountains and the number of spell types.

The second line contains \(n\) integers \(h_1, h_2, \ldots, h_n\) representing the initial heights of the mountains.

Then follow \(m\) lines. The \(i\)th of these lines contains two integers \(l_i\) and \(c_i\), indicating that there is a spell which can raise or lower the height of any contiguous segment of exactly \(l_i\) mountains by 1 (at a cost of \(c_i\) per use).

outputFormat

Output a single integer, the minimum total energy cost required to achieve a non-decreasing sequence of mountain heights while keeping every height nonnegative at all times. If it is impossible, output -1.

sample

3 1
3 1 2
2 1

2