G - 同意書 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

パ研合宿に参加するには、保護者の同意書が必要です。合宿に参加する人は 1 人 1 枚、同意書を提出しなければなりません。

今年のパ研合宿には N 人の人が参加します。各参加者には、1 から N までの番号が振られています。

ところで、Rho さん曰く、i=1,\ 2,\ldots,\ M について、以下のことが成り立っているそうです。

  • 参加者 l_i,\ l_i+1,\ldots,\ r_i のうち x_i 人が同意書を既に提出している。

Rho さんの発言に矛盾がないか判定した上で、なければ既に同意書を出している人の数の最大値を求めてください。

制約

  • 入力は全て整数である。
  • 1\leq N\leq14
  • 1\leq M\leq N(N+1)/2
  • 1\leq l_i\leq r_i\leq N
  • 0\leq x_i\leq r_i-l_i+1
  • (l_i,\ r_i)≠(l_j,\ r_j)(i≠j)

入力

入力は以下の形式で標準入力から与えられます。

\(N\) \(M\)
\(l_1\) \(r_1\) \(x_1\)
\(l_2\) \(r_2\) \(x_2\)
\(⋮\)
\(l_M\) \(r_M\) \(x_M\)

出力

Rho さんの発言に矛盾がないなら既に同意書を出している人の数の最大値を、矛盾があるなら -1 を出力してください。 出力の最後に改行を忘れないでください。

入力例1

3 2
1 2 1
1 1 0

出力例1

2

Rho さんの証言に矛盾しないのは、以下の 2 通りです。

  1. 参加者 2,\ 3 が既に同意書を出している。
  2. 参加者 2 が既に同意書を出している。
既に同意書を出している人の数が最大となるのは前者で、その数は 2 です。よって 2 を出力します。

入力例2

4 2
1 3 0
1 2 1

出力例2

-1

Rho さんの発言に矛盾があります。

入力例3

5 2
1 3 2
3 4 2

出力例3

4