普及-⏱ 1000ms💾 256MB#P3107🏷️ 前缀和模拟

题目描述

古镇老街长 $L$ 米,街道两端分别在数轴 $0$ 和 $L$ 处,每个整数点 $0,1,2,\cdots,L$ 都挂着一盏红灯笼,相邻两盏恰好间隔 1 米。

灯笼节开幕前,街道上有 $M$ 段区域要搭戏台。第 $i$ 段区域覆盖数轴区间 $[s_i, e_i]$(含两端点),搭台期间这些点上挂的灯笼必须全部摘下来。不同区段之间可能有重叠。

狂欢结束后要重新挂灯,先数一数:街上还剩多少盏灯笼?

输入格式

第一行两个整数 $L, M$,用空格分隔,表示街长与区段数。 接下来 $M$ 行,每行两个整数 $s, e$,用空格分隔,表示一段施工区域的起止坐标($0 \le s < e \le L$)。

输出格式

一行,一个整数,表示摘除后剩余的灯笼数。

数据范围

$$1 \le L \le 10000,\quad 1 \le M \le 100$$
对于 20% 的数据,区段之间互不重叠;其余数据区段之间可能重叠。

样例输入 #1
20 3
2 5
4 8
15 16
样例输出 #1
12
样例输入 #2
10 2
0 10
3 7
样例输出 #2
0