Minimum Developers Needed

You are given n tasks. Each task is described by three integers \(s_i\), \(d_i\), and \(h_i\):

• \(s_i\) is the start time of the task,
• \(d_i\) is the number of developers required for the task, and
• \(h_i\) is the duration of the task.

The same developer can work on different tasks at different times. Your goal is to determine the minimum number of developers required so that all tasks can be completed concurrently with sufficient manpower at all times.

Note: A task that starts at time \(s_i\) and lasts for \(h_i\) hours requires \(d_i\) developers for each hour in the interval \([s_i, s_i+h_i)\). The answer is the maximum number of developers needed at any given hour.

inputFormat

The input is read from standard input (stdin) and has the following format:

n
s_1 d_1 h_1
s_2 d_2 h_2
... 
s_n d_n h_n

Here, n is the number of tasks, and each of the following n lines contains three integers representing a task's start time, the number of developers required, and the duration of the task, respectively.

outputFormat

The output should be written to standard output (stdout) and consist of a single integer: the minimum number of developers required.

2
0 3 4
0 2 6

5