该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
给定 n 个区间 [ai,bi]和 n 个整数 ci 。
你需要构造一个整数集合 Z,使得∀i∈[1,n],Z中满足ai≤x≤bi的整数 x 不少于 ci 个。
求这样的整数集合 Z 最少包含多少个数。
输入格式
第一行包含2个整数m (bi 不超过m)和 n。
接下来n行,每行包含三个整数ai,bi,ci 。
输出格式
输出一个整数表示结果。
样例
输入样例
11 5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
输出样例
6
提示
1≤n≤50000,
0≤ai,bi≤50000,
1≤ci≤bi−ai+1