Max Performances

You are given a festival with a duration of \(T\) minutes. There are \(n\) artists available, each having a performance that starts at a specified time and runs for a certain duration. Your task is to determine the maximum number of non-overlapping performances that can be scheduled such that no performance extends beyond the festival's total duration \(T\).

A performance by an artist is defined by its start time \(s\) and its duration \(d\), which means it runs from time \(s\) to \(s+d\). A performance is considered valid only if \(s+d \leq T\). Two performances do not overlap if the start time of a performance is greater than or equal to the end time of the previously scheduled performance.

Your program should read input from standard input (stdin) and output the result to standard output (stdout).

inputFormat

The input is given as follows:

• The first line contains an integer \(T\) (\(1 \leq T \leq 10^9\)) representing the total duration of the festival.
• The second line contains an integer \(n\) (\(1 \leq n \leq 10^5\)) representing the number of artists.
• The following \(n\) lines each contain two integers: \(s\) (the start time) and \(d\) (the duration) of each artist's performance.

outputFormat

Output a single integer representing the maximum number of non-overlapping performances that can be scheduled.

300
4
30 100
120 150
180 90
240 50

2