問題文

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
• 入力は全て整数

入力例 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