#P1179. 牛奶桶分配(blist)
牛奶桶分配(blist)
题目描述
农场主约翰正在考虑改变分配牛奶桶的方式。他希望最终使用尽量少的牛奶桶,但他不确定到底最少有多少。请帮帮他!
农夫约翰有n头牛(1≤n≤100),为了编号方便,编号为1到n。第i头牛挤奶时间为si到ti,挤奶过程中需要使用bi个桶。几头牛可能会在同一时间挤奶;如果是这样,它们就不能用同一个桶。也就是说,在时间si和时间ti之间,分配给奶牛i挤奶的桶不能用于任何其他奶牛的挤奶。当然,这些桶也可以用在这个时间段之外的其他奶牛身上。为了简化他的工作,约翰已经确保在任何给定的时间点,最多只有一头奶牛的挤奶开始或结束(也就是说,所有si和ti都是不同的)。
约翰有一个储藏室,里面装着用标签1、2、3等顺序编号的桶。在他目前的挤奶策略中,每当有一头奶牛开始挤奶,约翰就会跑到储藏室,拿上标签编号最小的bi个桶,然后将它们分配给这头牛挤奶。
请确定约翰需要在他的储藏室里放多少桶才能成功地挤奶。
输入格式
输入的第一行包含n(1≤n≤100)。
接下来的n行分别描述一头牛,其中包含由空格分隔的数字si、ti和bi。si和ti都是1…1000范围内的整数,bi是1…10范围内的整数。
输出格式
输出一个整数,告诉约翰需要多少总存储桶。
样例
3
4 10 1
8 13 3
2 6 2
4
样例解释
在本样例中,约翰需要4个桶:他使用桶1和2为奶牛3挤奶(从时间2开始)。他用3号桶给1号奶牛挤奶(从时间4开始)。当第二头牛到达时间8时,桶1和2现在可用,所以不使用桶3,使用桶1、2和4。