We have N identification cards, numbered from 1 to N, and M gates. The i-th gate can be passed by any card whose number lies in the inclusive range [L_i, R_i]. Find the number of cards that can pass through all M gates individually.

Input is given on standard input in the following format:

N M
L1 R1
L2 R2
...
LM RM

Print a single integer: the count of identification cards that satisfy all gate requirements.

Eaxmples

Input 1

4 2
1 3
2 4

Output 1

2

Input 2

10 3
3 6
5 7
6 9

Output 2

1

Input 3

100000 1
1 100000

Output 3

100000

Constraints

• All input values are integers.
• 1 ≤ N ≤ 10^5
• 1 ≤ M ≤ 10^5
• 1 ≤ L_i ≤ R_i ≤ N

Solution approach

For a card to be accepted by every gate, its number must belong to the intersection of all the intervals [L_i, R_i]. The intresection of a set of intervals is itself an interval [L, R], where L is the maximum of all left endpoints and R is the minimum of all right endpoints. If L ≤ R, every integer in [L, R] is a valid card, and the answer is R - L + 1. If the intersection is empty (L > R), no card fulfills the requirements, and the output is 0.

Implementation

#include <iostream>
#include <algorithm>
#include <climits>

int main() {
    int total_cards, total_gates;
    std::cin >> total_cards >> total_gates;

    int max_left = 0;
    int min_right = INT_MAX;

    for (int i = 0; i < total_gates; ++i) {
        int left, right;
        std::cin >> left >> right;
        max_left = std::max(max_left, left);
        min_right = std::min(min_right, right);
    }

    int valid_count = min_right - max_left + 1;
    if (valid_count < 0) valid_count = 0;

    std::cout << valid_count << '\n';
    return 0;
}