← 返回题目列表

AtCoder · abc127_c

C. 监狱

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

我们有 N 身份证,还有 M 大门。

我们可以通过 i第一个门,如果我们有以下身份证之一: L_i-th, (L_i+1)-th,...,和 R_i第一张身份证。

有多少张身份证可以让我们独自通过所有的大门?

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq L_i \leq R_i \leq N

输入

输入由标准输入按以下格式给出:

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

输出

打印允许我们单独通过所有大门的身份证号码。


示例输入 1

4 2
1 3
2 4

示例输出 1

2

两张身份证可以让我们独自通过所有的大门,如下:

  • 第一张身份证不允许我们通过第二道门。
  • 第二张身份证可以让我们通过所有的大门。
  • 第三张身份证可以让我们通过所有的大门。
  • 第四张身份证不允许我们通过第一道门。

示例输入 2

10 3
3 6
5 7
6 9

示例输出 2

1

示例输入 3

100000 1
1 100000

示例输出 3

100000