A22731.种树

普及-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

一条街的一边有几座房子,因为环保原因居民想要在路边种些树。路边的地区被分割成块,并被编号成 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

    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
首页