Milk Buckets Allocation

Farmer John is re‐evaluating the way he assigns milk buckets to his cows during milking. He believes that by changing the strategy, he can use fewer buckets, but he is not sure how many exactly. Help him figure it out!

There are \(N\) cows (\(1 \le N \le 100\)), conveniently numbered from \(1\) to \(N\). The \(i\)th cow needs to be milked from time \(s_i\) to time \(t_i\) and requires \(b_i\) buckets throughout the milking period. Since multiple cows may be milked concurrently, buckets cannot be shared between cows that are being milked at the same time. In other words, if cow \(i\) uses a bucket from time \(s_i\) to \(t_i\), no other cow whose milking time overlaps with \([s_i, t_i]\) may use that bucket. However, a bucket can be reused once it is no longer in use.

Farmer John has a storage room with buckets numbered consecutively \(1, 2, 3, \dots\). According to his milking strategy, when a cow (say cow \(i\)) starts being milked at time \(s_i\), he fetches the smallest available \(b_i\) buckets from the storage and assigns them to that cow. It is guaranteed that at any moment, at most one cow starts or finishes milking (i.e. all \(s_i\) and \(t_i\) are distinct).

Your task is to determine the minimum number of buckets that need to be stored in the storage room so that Farmer John can milk all the cows following this strategy.

inputFormat

The first line contains a single integer \(N\) (\(1 \le N \le 100\)), representing the number of cows.

Each of the following \(N\) lines contains three integers \(s_i\), \(t_i\), and \(b_i\) describing the start time, finish time, and the number of buckets required by cow \(i\), respectively. It is guaranteed that all \(s_i\) and \(t_i\) are distinct and that at any moment at most one cow starts or finishes milking.

outputFormat

Output a single integer: the minimum number of buckets that must be stored so that the milking strategy can be carried out successfully.

sample

3
1 4 2
2 5 1
6 8 3

3