#T1423. 「一本通 1.1 例 2」种树

「一本通 1.1 例 2」种树

种树

题目背景

一条街的一边有几座房子,因为环保原因居民想要在路边种些树。

题目描述

路边的地区被分割成块,并被编号成 1,2,,n1, 2, \ldots,n。每个部分为一个单位尺寸大小并最多可种一棵树。

每个居民都想在门前种些树,并指定了三个号码 bbeett。这三个数表示该居民想在地区 bbee 之间(包括 bbee)种至少 tt 棵树。

居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。

输入格式

输入的第一行是一个整数,代表区域的个数 nn

输入的第二行是一个整数,代表房子个数 hh

33 到第 (h+2)(h + 2) 行,每行三个整数,第 (i+2)(i + 2) 行的整数依次为 bi,ei,tib_i, e_i, t_i,代表第 ii 个居民想在 bib_ieie_i 之间种至少 tit_i 棵树。

输出格式

输出一行一个整数,代表最少的树木个数。

样例 #1

样例输入 #1

9
4
1 4 2
4 6 2
8 9 2
3 5 2

样例输出 #1

5

提示

数据规模与约定

对于 100%100\% 的数据,保证:

  • 1n3×1041 \leq n \leq 3 \times 10^41h5×1031 \leq h \leq 5 \times 10^3
  • 1biein1 \leq b_i \leq e_i \leq n1tieibi+11 \leq t_i \leq e_i - b_i + 1