Panoramic Photo

Farmer John wants to create a panoramic photo featuring his N cows (numbered 1 through \(N\), with \(1\leq N\leq 200{,}000\)). He took \(M\) photos (\(1\leq M\leq 100{,}000\)), each of which captures a contiguous segment of cows. In photo \(i\) the cows numbered from \(a_i\) to \(b_i\) (inclusive) appear. Note that not every cow need appear in some photo.

After taking the photos, Farmer John observed something curious: each photo contains exactly one cow with spots. Although he always knew there were some spotted cows in his herd, he had never counted them. Based on the photos, please determine the maximum possible number of spotted cows that could exist in his herd. Print -1 if there is no possible assignment of spots to cows consistent with the photographic results.

More formally, let \(x_i\) be a binary variable for cow \(i\) (\(1 \le i \le N\)) where \(x_i=1\) indicates that cow \(i\) is spotted and \(x_i=0\) indicates it is not. For each photo \(i\) (with range \([a_i,b_i]\)), we require that \[ \sum_{j=a_i}^{b_i} x_j = 1. \] Additionally, cows that do not appear in any photo can be arbitrarily assigned spots. Under these conditions, compute the maximum possible \(\sum_{i=1}^{N} x_i\) (i.e. the maximum number of spotted cows) or output \(-1\) if no valid assignment exists.

inputFormat

The first line contains two integers \(N\) and \(M\) separated by a space.

Each of the following \(M\) lines contains two integers \(a_i\) and \(b_i\) (with \(1\le a_i\le b_i\le N\)), indicating that the \(i\)th photo contains cows numbered from \(a_i\) to \(b_i\) inclusive.

outputFormat

Print a single integer: the maximum possible number of spotted cows that could exist, or \(-1\) if no valid assignment exists.

sample

5 2
2 2
4 4

5