Covered Length on a Line Segment

Consider a horizontal line segment \(L\) of length \(d\) positioned along the \(x\)-axis with its left endpoint at the origin, i.e. \(L = [0,d]\). In the same plane, there are \(n\) vertical segments \(l_1,l_2,\dots,l_n\). For the \(i\)-th segment, its foot lies on \(L\) at \(x=x_i\) and it extends upward to height \(h_i\); hence its top is located at \((x_i, h_i)\).

Some (or all) of these vertical segments have a point light source placed at their top (the size of the light source is negligible). Each light source can emit a laser ray either to the left or to the right. A laser travels along a straight line and cannot cross (i.e. pass through) any segment (this includes the horizontal segment \(L\) as well as any of the vertical segments).

A point \(A\) on \(L\) is said to be covered if there exists at least one light source (placed on the top of some vertical segment) such that the laser ray it emits in one of the two horizontal directions eventually reaches \(A\) without being blocked by any segment.

Your task is to compute the total length of \(L\) that is covered by at least one such laser ray.

Observation: It can be shown that regardless of the positions \(x_i\) and heights \(h_i\) of the vertical segments, the lasers can always be oriented so that the entire segment \(L\) is covered. In other words, there is always a way to cover the entire interval \([0,d]\) by appropriately choosing the firing directions from the light sources. Therefore, the answer is always \(d\).

Note: Every vertical segment’s light source shoots a laser. When computing the coverage from an emitter located at \((x_i,h_i)\), one might analyze the unobstructed ray to a point \(p\) on \(L\) by requiring that the ray from \((x_i,h_i)\) to \((p,0)\) remains strictly above the top of every vertical segment that lies between \(x_i\) and \(p\). A short analysis shows that the leftmost emitter covers from \(0\) up to some point and the rightmost emitter covers from some point up to \(d\); moreover, the intervals contributed by the various emitters overlap so that the overall covered region is exactly \([0,d]\).

inputFormat

The input consists of multiple lines. The first line contains two integers \(d\) and \(n\) (where \(1 \le n\le 10^5\) and \(1 \le d \le 10^9\)). Each of the next \(n\) lines contains two positive integers \(x_i\) and \(h_i\), representing the horizontal coordinate of the foot of the \(i\)-th vertical segment and its height, respectively. It is guaranteed that \(0 < x_i < d\) for each \(i\).

outputFormat

Output a single number representing the total length of \(L\) that is covered. According to the analysis, the answer is always \(d\).

sample

10 1
5 5

10