H - AtCoder Hotel Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : {500} 点

問題文

高橋くん一行は、AtCoder Land に行くためにランド内にあるホテルに泊まることにしました。

N 人の人と M 個のランクが付いた部屋があります。

i 番目の人はランクが A_i 以上の部屋に泊まりたいと考えています。

また、i 番目の部屋のランクは R_i、定員は B_i 人、客室料金は C_i 円です。 C_i 円払うことで、B_i 人以下であれば何人でも i 番目の部屋に泊まることができます。

N 人全員が部屋に泊まることが可能か判定し、可能な場合必要な金額の総和の最小値を求めてください。

制約

  • 1\leq N,M \leq 5000
  • 1\leq A_i,R_i,B_i,C_i \leq 5000
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 \ldots A_N
R_1 B_1 C_1
\vdots
R_M B_M C_M

出力

N 人全員が部屋に泊まることが可能な場合、必要な金額の総和の最小値を X 円とする。このとき X を出力せよ。

不可能な場合 -1 を出力せよ。

入力例 1

4 3
3 5 1 4
5 3 3
3 1 1
2 3 2

出力例 1

4

1 番目の人が 2 番目の部屋に泊まり、それ以外の人が 1 番目の部屋に泊まることを考えます。

このとき必要な金額の総和は 4 となり、これが最小であることが示せます。

入力例 2

8 5
2 5 1 5 2 1 2 4
4 2 5
7 2 4
7 4 2
1 4 7
3 3 8

出力例 2

11

入力例 3

10 1
1 1 1 1 1 1 1 1 1 1
10 4 1

出力例 3

-1

N 人全員が部屋に泊まることはできません。