← 返回题目列表

AtCoder · typical90_aw

049. 翻转数字2(★6)

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

配点: 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