1606: 星际列车的座位

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:26 Solved:4

Description

    小明设计了星际宽体列车的座位如下图示。长长的列车共有n排座位,每一排共有10个座位,编号从1到10。

        给你 m个数的数组 seats的数据 ,包含所有已经被预约了的 m个座位。比如说,seats[i]=[3 8] ,它表示第 3 排第 8 个座位被预约了。

       请你返回 最多能安排多少个 4 人家庭 。4 人家庭要占据 同一排内连续 的 4 个座位。隔着过道的座位(比方说 [33] 和 [34])不是连续的座位,但是如果你可以将 4 人家庭拆成过道两边各坐 2 人,这样子是允许的。

示例 1:


  输入:n = 3 reservedSeats = [[1 2][1 3][1 8][2 6][3 1][3 10]]
  输出:4 解释:上图所示是最优的安排方案,总共可以安排 4 个家庭。蓝色的叉表示被预约的座位,橙色的连续座位表示一个 4 人家庭。

Input

输入第一行为 n 与 m , n为列车有 n排座位,m为己被预约的座位数。其后m行,每行两个数,前一数为己预约的排教,后一数为座位号。数字间空一格。

Output

        输出一个正整数,为最多能安排 4人家庭的数目。

Sample Input Copy

3 6
1 2
1 3
1 8
2 6
3 1
3 10

Sample Output Copy

4

HINT

  • 1 <= n <= 10^9;  1=< m <=10^6