← 返回题目列表

AtCoder · codequeen2024_final_e

H. AtCoder 酒店

中文机器翻译题面 查看原题

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