题目描述

汪老师在做菜，有 $N$ 种菜品可以选择制作，编号从 $1$ 到 $N$ 。

第 $i(1 \le i \le N)$ 道菜的价值为 $V_i$ ，制作时消耗香料。消耗的香料量可以在 $L_i$ 到 $R_i$ 之间调节。

判断以下事项是否可行，如果可行，请输出可以制作的菜品的总价值的最大值。

从 $N$ 种菜品中选择几种，每种制作恰好一道菜，并且它们总共消耗恰好 $W$ 的香料。

输入格式

第一行，两个整数 $W$ 和 $N$，以空格分隔。

接下来 $N$ 行，每行包含三个整数 $L_i$，$R_i$ 和 $W_i$，以空格分隔。

输出格式

请输出可以制作的菜品的总价值的最大值。

如果无法恰好消耗 $W$ 的香料，请输出 $-1$ 。

样例

100 4
30 40 120
30 40 30
30 40 1500
30 40 40

1660

100 4
13 15 31415
12 13 92653
29 33 58979
95 98 32384

-1

10000 20
4539 6002 485976
1819 5162 457795
1854 2246 487643
1023 4733 393530
1052 6274 289577
1874 2436 167747
1457 4248 452660
2103 4189 174955
3057 5061 319316
4898 4953 394627
1313 2880 154687
1274 1364 259598
3866 5844 233027
1163 5036 386223
1234 4630 155972
2845 4978 442858
3168 5368 171601
3708 4407 394899
3924 4122 428313
2112 4169 441976

2727026

说明/提示

样例 1 解释

选择第 $1$，$3$，$4$ 种菜品个制作一道菜，每道菜均消耗 $\frac{100}{3}$ 的香料。总价值为 $120 = 1500 + 40 = 1660$。

数据范围与约定

• $1 \leq W \leq 10^4$
• $1 \leq N \leq 500$
• $1 \leq L_i \leq R_i \leq W$ $(1 \leq i \leq N)$
• $1 \leq V_i \leq 10^9$ $(1 \leq i \leq N)$
• 输入均为整数