最少补光点

题目描述

一条走廊共有 n 个位置，编号为 1 到 n。现在有 m 段位置已经被自然光照亮。每一段自然光区间用 [l,r] 表示，保证输入时这些区间已经按左端点从小到大给出，且两段区间互不重叠。

现在你可以安装人工灯。若在位置 x 安装一盏灯，则它能照亮区间 [x-1,x+1]，也就是最多连续 3 个位置。

请你计算，最少还需要安装多少盏灯，才能让 1 到 n 的所有位置都被照亮。

输入格式

第一行输入两个整数 n、m。 接下来 m 行，每行输入两个整数 l、r，表示一段已经被照亮的区间。

输出格式

输出一个整数，表示最少还需要安装的灯数。

数据范围与约定

1≤n≤10$^9$ 0≤m≤2×10$^5$ 1≤l≤r≤n 输入保证所有区间已经按左端点升序给出，且互不重叠

样例

10 1
3 5

3