#272. 区间

区间

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定 n\red {n} 个区间 [ai,bi]\red {[a_i ,b _i ]}n\red {n} 个整数 ci\red {c _i}

你需要构造一个整数集合 Z\red {Z},使得i[1,n]\red {∀i∈[1,n]},Z\red Z 中满足aixbi\red {a _i≤x≤b_i}的整数 x\red {x} 不少于 ci\red {c_i} 个。

求这样的整数集合 Z\red {Z} 最少包含多少个数。

输入格式

第一行包含2\red{2}个整数m\red{m}bi\red{b_i} 不超过m\red{m})和 n\red {n}

接下来n\red {n}行,每行包含三个整数ai,bi,ci\red {a _i ,b _i ,c_i}

输出格式

输出一个整数表示结果。

样例

输入样例

11 5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

输出样例

6

提示

1n50000\red {1≤n≤50000},

0ai,bi50000\red {0≤a _i ,b _i ≤50000},

1cibiai+1\red {1≤c _i ≤b_i −a _i +1}

高中组测试

未参加
状态
已结束
规则
ACM/ICPC
题目
4
开始于
2022-4-7 15:45
结束于
2022-4-11 19:45
持续时间
100 小时
主持人
参赛人数
18