梨には豊富なビタミンが含まれており、非常に健康に良い果物と言えます。

名探偵・江戸川コナンは、なぜ不老不死であり、行く先々で人が亡くなるような事件に遭遇するのでしょうか？その秘訣は、毎日「雪梨枸杞湯（梨とクコの実のスープ）」を飲んでいるからだと言われています。しかし、長年彼に梨を卸していた業者が亡くなってしまい、彼は仕方なく露天商から梨を買い集めることになりました。

江戸川コナンはこれからの $n$ 日間の梨の供給を計画する必要があります。第 $i$ 日目には、健康維持のために $a_i$ 個の梨が必要です。

コナンは探偵の旅の途中で $m$ 人の商人と出会います。第 $i$ 番目の商人と出会うのは第 $t_i$ 日目であり、その商人は合計で $b_i$ 個の梨を販売できます。梨はあまり新鮮ではないため、合計で $k_i$ 日経つと腐ってしまいます。つまり、コナンが購入した場合、その梨は第 $t_i$ 日から第 $t_i + k_i - 1$ 日までの間しか食べることができません。

総費用が最小となるような購入計画を立ててください。

入力

1行目に2つの正整数 $n, m$ が与えられます。それぞれ日数と商人の数を表します。

2行目に $n$ 個の正整数 $a_i$ が与えられます。

続く $m$ 行の各行には、4つの整数 $b_i, c_i, t_i, k_i$ が与えられます。それぞれ販売上限数、単価、販売日、および新鮮さ（食べられる期間）を表します。

出力

計画が可能であれば、最小費用を出力してください。

解が存在しない場合は $-1$ を出力してください。

入出力例

入力 1

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

出力 1

38

制約

• $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 点): $1 \le n \le 50, 1 \le m \le 100$
• Subtask 2 (55 点): $1 \le n \le 1000, 1 \le m \le 2000$