問題文

$N$ 個の宝箱があります．これらの宝箱には，宝箱 $1$，宝箱 $2$，……，宝箱 $N$ という風に番号がついています．このうちいくつか（ $0$ 個かも，全部かもしれません）は本物で財宝が入っていますが，残りは偽物で開けると即死の罠が張られています．

この宝箱について，$M$ 種類の情報がわかっています．$i$ 種類目の情報は，$3$ つの整数 $L_i, R_i, C_i$ によって次のように表されます．

• $i$ 種類目の情報：番号が $L_i$ 以上 $R_i$ 以下の宝箱のうち，本物の宝箱は $C_i$ 箱．

与えられる情報には矛盾がないことが保証されます．

偽物の宝箱を開けると死んでしまうので，ジョーチくんは本物の宝箱とわかるものだけを選んで開けることにしました．

与えられた情報をもとに，確実に 本物である宝箱がいくつあるか求めてください．

ただし，ある宝箱が確実に本物であるとは，情報に合致する宝箱の本物/偽物の組合せであって，その宝箱が偽物であるような場合が存在しないことを言います．

制約

• 入力はすべて整数
• $1 \leq N \leq 15$
• $1 \leq M \leq 100$
• $1 \leq L_i \leq R_i \leq N$
• $0 \leq C_i \leq R_i - L_i + 1$
• 与えられる情報に矛盾はない．

入力

N M
L_1 R_1 C_1
.
.
.
L_M R_M C_M

出力

確実に本物である宝箱の個数を出力してください．

サンプル

5 3
1 2 2
3 4 1
4 5 0

3

$1$ つ目の情報から，番号 $1$ 以上 $2$ 以下の宝箱のうち $2$ つが本物であることがわかるので，宝箱 $1$ と $2$ はともに本物です．

$2$ つ目の情報から，宝箱 $3$ と $4$ のうちどちらか $1$ つが本物であることがわかります．$3$ つ目の情報から，宝箱 $4$ と $5$ はどちらも偽物なので，これらの情報を合わせて考えると，宝箱 $3$ が確実に本物であるとわかります．

よって，確実に本物であるとわかる宝箱は $3$ つです．

5 1
1 5 4

0

情報から，番号が $1$ 以上 $5$ 以下の宝箱のうち $4$ つが本物であるとわかりますが，与えられた情報だけではどれも確実に本物であるとは言えません．

よって，答えは $0$ です．

15 13
7 9 1
12 14 2
2 13 5
8 14 4
9 12 2
13 15 2
10 11 1
15 15 1
5 6 0
3 5 1
5 12 3
1 10 5
1 11 5

7