Chúng ta có \(N\) thẻ ID, và có \(M\) cổng.

Chúng ta có thể qua được cổng thứ \(i\) nếu chúng ta có một trong các thẻ ID sau: thẻ ID thứ \(L_i\), \((L_i + 1)\), ..., và thẻ ID thứ \(R_i\).

Có bao nhiêu thẻ ID cho phép chúng ta qua tất cả các cổng một mình?

Ràng buộc

• Tất cả các giá trị đầu vào là số nguyên.
• \(1 \leq N \leq 10^5\)
• \(1 \leq M \leq 10^5\)
• \(1 \leq L_i \leq R_i \leq N\)

INPUT FORMAT

Đầu vào được cung cấp từ Standard Input theo định dạng sau:

N
M
L_1 R_1
L_2 R_2
...
L_M R_M

OUTPUT FORMAT

In ra số lượng thẻ ID cho phép chúng ta qua tất cả các cổng một mình.

Ví dụ:

Input

4 2
1 3
2 4

Output

2

Hai thẻ ID cho phép chúng ta qua tất cả các cổng một mình, như sau:

• Thẻ ID thứ nhất không cho phép qua cổng thứ hai.
• Thẻ ID thứ hai cho phép qua tất cả các cổng.
• Thẻ ID thứ ba cho phép qua tất cả các cổng.
• Thẻ ID thứ tư không cho phép qua cổng thứ nhất.

Input

10 3
3 6
5 7
6 9

Output

1

Giải thích ví dụ mẫu

Ví dụ 1:

• Input:

  4 2 1 3 2 4

• Giải thích:

  • Thẻ ID 2 và 3 cho phép qua tất cả các cổng, trong khi thẻ ID 1 và 4 không cho phép.

Ví dụ 2:

• Input:

  10 3 3 6 5 7 6 9

• Giải thích:

  • Chỉ thẻ ID 6 cho phép qua tất cả các cổng, vì nó nằm trong các khoảng cho phép.
    

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House