The Bucket List#10394
Farmer John is considering a change in how he allocates buckets for milking his cows. He thinks this will ultimately allow him to use fewer buckets in total, but he is not sure exactly how many he will need. Please help him out!
Farmer John has cows, conveniently numbered . The -th cow must be milked from time s_i to time t_i and requires b_i buckets during the milking process. Several cows may be milked at the same time; in that case, they cannot share buckets. That is, a bucket assigned to cow cannot be used to milk any other cow between time s_i and time t_i. Of course, the bucket can be used for other cows outside this time interval. To simplify his job, FJ has made sure that at any moment, the milking of at most one cow starts or ends (that is, all the values s_i and t_i are distinct).
FJ has a storage room containing buckets numbered sequentially with labels , , , and so on. Under his new milking strategy, whenever some cow starts being milked (at time s_i), FJ runs to the storage room, takes the b_i available buckets with the smallest labels, and allocates them to cow .
Determine the total number of buckets FJ needs to keep in his storage room in order to milk all the cows successfully.
The first line contains an integer n~(1 \le n \le 100). Each of the next lines describes one cow and contains three integers s_i, t_i, and b_i~(1 \le s_i, t_i \le 1000, 1 \le b_i \le 10).
Print one integer — the total number of buckets FJ needs.
In this example, FJ needs buckets. He uses buckets and to milk cow (starting at time ) and bucket to milk cow (starting at time ). When cow arrives at time , buckets and are available again, but bucket is not, so he uses buckets , , and .
Example 1