Pears are rich in vitamins and can be considered a very healthy fruit.

How does the famous detective Conan Edogawa manage to stay young forever, while people lose their lives wherever he goes? The secret is that he drinks pear and goji berry soup every day. However, the supplier who had been wholesaling pears to him for a long time has unfortunately passed away, so he has to make do with buying retail pears from street vendors.

Conan Edogawa needs to plan his pear supply for the next $n$ days. On day $i$, he needs $a_i$ pears for his health.

During his travels to solve cases, Conan will encounter $m$ vendors. The $i$-th vendor is encountered on day $t_i$. The vendor can sell a total of $b_i$ pears at a unit price of $c_i$, and since the pears might not be very fresh, they will spoil after a total of $k_i$ days. That is, if Conan buys them, he can only consume them from day $t_i$ to $t_i + k_i - 1$.

Please plan his purchasing strategy to minimize the total cost.

Input Format

The first line contains two positive integers $n$ and $m$, representing the number of days and the number of vendors.

The second line contains $n$ positive integers $a_i$.

The next $m$ lines each contain four integers $b_i, c_i, t_i, k_i$, representing the sales limit, unit price, encounter day, and freshness duration, respectively.

Output Format

If a plan is possible, output the minimum cost.

If there is no solution, output $-1$.

Examples

Input 1

3 3
3 5 4
6 1 1 3
3 10 1 2
4 3 2 2

Output 1

38

Constraints

$1 \le n \le 1000$, $1 \le m \le 2000$, $1 \le a_i, b_i, c_i \le 1000$, $1 \le t_i, k_i, t_i + k_i - 1 \le n$

Subtask 1 (45 pts.): $1 \le n \le 50, 1 \le m \le 100$

Subtask 2 (55 pts.): $1 \le n \le 1000, 1 \le m \le 2000$