Problem 6062. -- [Usaco2018 Dec]The Bucket List

6062: [Usaco2018 Dec]The Bucket List

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 4  Solved: 4
[Submit][Status][Web Board]

Description

Farmer John正在考虑改变他给奶牛挤奶的时候分配牛奶桶的方式。他认为这最终能使得他使用数量更少的桶,然
而他不清楚具体是多少。请帮助他!Farmer John有N头奶牛(1≤N≤100),方便起见编号为1…N。 第i头奶牛需
要从时间si到时间ti之间挤奶,并且挤奶过程中需要用到bi个桶。于是多头奶牛可能在同一时刻都在挤奶;如果这
样,她们不能使用相同的桶。也就是说,一个在第i头奶牛挤奶时用的桶不可以被任何在时间si到时间ti之间挤奶
的其他奶牛使用。当然,这个桶在这段时间之外可以被其他奶牛所使用。为了简化他的工作,FJ保证在任一时刻,
至多只有一头奶牛开始或是结束挤奶(也就是说,所有的si和ti各不相同)。FJ有一个储藏室,里面有依次编号为
1、2、3、……的桶。在他的挤奶策略中,当某一头奶牛(比如说,奶牛i)开始挤奶(在时间si),FJ就跑到储藏
室取出编号最小的bi个桶分配给第i头奶牛用来挤奶。请求出FJ需要在储藏室中存放多少个桶才能使得他能够顺利
地给所有奶牛挤奶。

Input

输入的第一行包含N。
以下N行,每行描述了一头奶牛,包含三个空格分隔的数si,ti,和bi。 
其中si和ti均为1…1000之间的整数,bi为1…10之间的整数。

Output

输出一个整数,为FJ需要的桶的数量。

Sample Input

3
4 10 1
8 13 3
2 6 2

Sample Output

4
在这个例子中,FJ需要4个桶:他用桶1和桶2来给奶牛3挤奶(从时间2开始)。他用桶3给奶牛1挤奶(从时间4开始
)。当奶牛2在时间8开始挤奶时,桶1和桶2可以再次利用,然而桶3不可以,所以他会使用桶1、桶2和桶4

HINT

Source

[Submit][Status]