問題文

株式会社 KYOPRO-MASTER で働いている太郎君は、今後 D 日間の労働計画を立てることにしました。 彼は今期の人事評価を上げるため、より多く働きたいと思っています。 しかし、働きすぎると労働基準監督署に怒られてしまいます。具体的には、i = 1,2, ... ,N に対して、以下の条件を満たす必要があります。

• 条件 i：L_i ～ R_i 日目について、最も多く働いた日でも H_i 時間以下

太郎君の D 日間の合計労働時間として考えられる最大値は何時間でしょうか。ただし、1 日は 24 時間であるものとします。

制約

• 1 \leq D \leq 365
• 0 \leq N \leq 10000
• 1 \leq L_i \leq R_i \leq D
• 10 \leq H_i \leq 24
• 入力はすべて整数

入力例 1

5 3
1 2 22
2 3 16
3 5 23

出力例 1

100