← 返回题目列表

AtCoder · pakencamp_2020_day1_g

G. 同意书

中文机器翻译题面 查看原题
配点 : 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