配点 : {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 不是每个人都可以留在房间里。