493. Allocate Bus Seats

0

Medium

A bus has n rows of seats, numbered from 1 to n and there are ten seats in each row, labelled from 1 to 10. Given the list of reservedSeats containing the numbers of seats already reserved, for example, reservedSeats[i] = [3,8] means the seat located in row 3 and labelled with 8 is already reserved. Return the maximum number of four-person groups you can assign on the bus seats. A four-person group occupies four adjacent seats in one single row. Seats across an aisle (such as [3,3] and [3,4]) are not considered to be adjacent, but there is an exceptional case on which an aisle split a four-person group, in that case, the aisle split a four-person group in the middle, which means to have two people on each side.

Input Format

First line of input contains two integer n and m, number of rows and number of reserved seats.
Following m line contains two integer i and j representing that seat located in row 3 and labelled with 8 is already reserved.

Output Format

Return single integer the maximum number of four-person groups you can assign on the bus seats.

Example

Input

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

Output

4

Constraints

• 1 <= n <= 10^9
• 1 <= reservedSeats.length <= min(10*n, 10^4)
• reservedSeats[i].length == 2
• 1 <= reservedSeats[i][0] <= n
• 1 <= reservedSeats[i][1] <= 10
• All reservedSeats[i] are distinct.