Princess Waiting Time

A number of knights have scheduled visits to see the king. Each knight makes an appointment with a reserved starting time \(t_i\) and a visiting duration \(d_i\). The knights are processed in the order recorded at the reception desk. This means that the \(i\)th knight starts his visit at \(\max(t_i, F_{i-1})\), where \(F_{i-1}\) is the finish time of the previous knight (with \(F_0 = 0\)), and finishes at time \(F_i = \max(t_i, F_{i-1}) + d_i\).

The princess has also reserved a visiting time \(P\). However, out of courtesy she does not want to disturb the knights' order, so she will only visit the king after all the knights have finished. Your task is to calculate how long the princess must wait. In other words, if all knights finish at time \(F_n\), the waiting time is \(\max(0, F_n - P)\).

inputFormat

The first line contains two integers \(P\) and \(n\) separated by a space, where \(P\) (\(0 \leq P \leq 10^9\)) is the princess's reserved visiting time and \(n\) (\(0 \leq n \leq 10^5\)) is the number of knights.

Each of the next \(n\) lines contains two integers \(t_i\) and \(d_i\) (\(0 \leq t_i, d_i \leq 10^9\)), representing the reserved starting time and the visiting duration for the \(i\)th knight. The knights are given in the order of their recorded visiting times.

outputFormat

Output a single integer representing the waiting time the princess must endure before she can visit the king.

sample

4 3
2 3
5 3
8 2

6