当前没有测试数据。

‌题目背景

尼斯湖的莴笋子是一种会隐身的魔法蔬菜精灵，它们每天会浮出水面晒太阳，但湖底的警卫水獭会每隔 $T$ 秒突然回头扫视湖面！你必须编写一个程序，在时间轴中选择合适的莴笋子采集，使得总美味值最大且不被警卫发现。如果莴笋子的采集时间‌完全包含在警卫两次回头之间的间隔‌中，则视为安全采集，否则会被警卫发现并把你吃了！

题目描述

‌ 警卫水獭第一次回头时间为 $0$，之后每隔 T 秒回头一次（即回头时间点为 $0, T, 2T, 3T \dots$）。 每个莴笋子有三个属性：出现时间 $S$、消失时间 $E$、美味值 $V$。 只有当 ‌$​[S, E]​$‌ 完全包含在某个警卫回头间隔 ‌$[k \times T, (k+1) \times T)$​ 内时，采集该莴笋子才是安全的。

请计算你能偷吃的莴笋子的最大美味值之和。若所有莴笋子都无法安全采集，请输出 -1。

输入格式‌

• 第一行两个整数 $T$（警卫回头间隔）和 $n$（莴笋子数量）
• 接下来 $n$ 行，每行三个整数 $S_i, E_i, V_i$

输出格式‌

• 最大安全美味值之和，或-1 ‌

样例

1 3 7
6 8 5
11 13 3

15

‌

3 2
0 2 10
4 6 20

-1

‌

数据范围

对于$100\%$的数据：$1 \leq V_i \leq 10^5$