AT_codequeen2024_final_e AtCoder Hotel

高桥等人为了去 AtCoder Land，决定入住园区内的酒店。 现在有 $N$ 个人和 $M$ 个带有等级的房间。 第 $i$ 个人希望入住等级不低于 $A_i$ 的房间。 第 $i$ 个房间的等级为 $R_i$，最大容纳人数为 $B_i$，房费为 $C_i$ 日元。每间房间只需支付 $C_i$ 日元，就能让至多 $B_i$ 个人入住。 请判断 $N$ 个人是否都能入住房间。如果可以，求所需总金额的最小值。

输入数据通过标准输入给出，格式如下： > $N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$ $R_1$ $B_1$ $C_1$ > $R_2$ $B_2$ $C_2$ > $\vdots$ > $R_M$ $B_M$ $C_M$

如果 $N$ 个人都可以入住，请输出最小总费用 $X$（日元）。 如果无法让 $N$ 个人都入住，请输出 $-1$。

### 样例解释 1 可以让第 $1$ 个人住进第 $2$ 个房间，其余人住进第 $1$ 个房间。 此时所需总费用为 $4$，且可以证明这是最小值。 ### 样例解释 3 无法让 $N$ 个人全部入住房间。 ### 数据范围 - $1\leq N,M \leq 5000$ - $1\leq A_i,R_i,B_i,C_i \leq 5000$ - 输入均为整数。 由 ChatGPT 5 翻译