AT_codequeen2024_final_e AtCoder Hotel

高橋くん一行は、AtCoder Land に行くためにランド内にあるホテルに泊まることにしました。 $ N $ 人の人と $ M $ 個のランクが付いた部屋があります。 $ i $ 番目の人はランクが $ A_i $ 以上の部屋に泊まりたいと考えています。 また、 $ i $ 番目の部屋のランクは $ R_i $ 、定員は $ B_i $ 人、客室料金は $ C_i $ 円です。 $ C_i $ 円払うことで、 $ B_i $ 人以下であれば何人でも $ i $ 番目の部屋に泊まることができます。 $ N $ 人全員が部屋に泊まることが可能か判定し、可能な場合必要な金額の総和の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ \ldots $ $ A_N $ $ R_1 $ $ B_1 $ $ C_1 $ $ \vdots $ $ R_M $ $ B_M $ $ C_M $

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

### Sample Explanation 1 $ 1 $ 番目の人が $ 2 $ 番目の部屋に泊まり、それ以外の人が $ 1 $ 番目の部屋に泊まることを考えます。 このとき必要な金額の総和は $ 4 $ となり、これが最小であることが示せます。 ### Sample Explanation 3 $ N $ 人全員が部屋に泊まることはできません。 ### Constraints - $ 1\leq N,M \leq 5000 $ - $ 1\leq A_i,R_i,B_i,C_i \leq 5000 $ - 入力は全て整数