配点: 6 点
問題文
E869120 你是长度 N 的位串
我有 S 。起初,S 中的所有字符都是 0 。
ABC 商店有
有 M 件商品出售,每件
它们的编号最大为 1 假设一直下雨,直到 M 。项目 i 的价格是 C_i 是日元,使用这个 S 的 L_i 〜 R_i 字符将被反转。也就是说,S 的 L_i 〜 R_i 角色中,0 是什么 1 到,
1 是什么 0 。
E869120 你是 我想选择并购买一些M 商品,以满足以下条件。
条件 什么长度 N 的位串 我有 T (总计 2^N 有很多方法可以做到这一点),但您也可以根据需要多次“选择并使用已购买的物品”(0 次) 可以匹配S 在 T 可以匹配到
求他满足条件需要购买的物品的最低总价。
但是,如果您购买所有商品后仍无法满足条件,请举报。
制約
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq C_i \leq 10^9
- 1 \leq L_i \leq R_i \leq N
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N M C_1 L_1 R_1 C_2 L_2 R_2 \vdots C_M L_M R_M
出力
如果您购买所有物品后仍无法满足条件,-1 请输出。
如果没有,请打印满足条件所需购买的商品 E869120 的最低总价。
入力例 1
2 3 1 1 1 1 2 2 10 1 2
出力例 1
2
项目 让我们考虑一下您购买 1, 2 的情况。 例如,如果对
各 T 执行以下操作 您可以匹配 S 在 T 。
- T=
00:什么也不做 - T=
01:项目 使用 2 使用 - T=
10:项目 使用 1 使用 - T=
11:项目 使用 1 ,然后使用该项目 2 使用
那么总价是 1 + 1 = 2 圆圈,这是最小值。 可能有多个项目具有相同的
入力例 2
2 3 1 1 1 10 2 2 1 1 2
出力例 2
2
项目 让我们考虑一下您购买 1, 3 的情况。 例如,如果对
各 T 执行以下操作 您可以匹配 S 在 T 。
- T=
00:什么也不做 - T=
01:项目 使用 3 ,然后使用该项目 1 使用 - T=
10:项目 使用 1 使用 - T=
11:项目 使用 3 使用
那么总价是 1 + 1 = 2 圆圈,这是最小值。 可能有多个项目具有相同的
入力例 3
4 5 3 1 2 5 2 4 9 3 4 4 1 4 8 2 4
出力例 3
-1
(L_i,R_i) 。
入力例 4
9 11 10 2 7 100 1 6 1 2 8 39 4 5 62 3 4 81 1 3 55 8 8 91 5 5 14 8 9 37 5 5 41 7 9
出力例 4
385