#P6244. Maximum Activities

    ID: 19463 Type: Default 1000ms 256MiB

Maximum Activities

Maximum Activities

Farmer John (FJ) is participating in an event. He wishes to attend as many activities as possible out of a total of N events. After finishing one event, he can immediately start the next one. Each activity is described by its start time T and its duration L. Note that FJ never leaves an event early.

Your task is to determine the maximum number of events FJ can attend. The finish time of an event is given by \(T + L\). FJ can attend an event if its start time is not earlier than the finish time of the previously attended event.

Input Format: The input begins with an integer \(N\) - the number of events. Each of the following \(N\) lines contains two integers \(T\) and \(L\), representing the start time and duration of an event respectively.

Output Format: Print a single integer representing the maximum number of events FJ can attend.

inputFormat

The first line contains an integer \(N\) (the number of events). Each of the next \(N\) lines contains two space-separated integers, \(T\) and \(L\), where \(T\) is the start time and \(L\) is the duration of that event.

outputFormat

Output a single integer which is the maximum number of events FJ can attend.

sample

3
1 3
2 2
4 3
2

</p>