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.

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

Loading...

View Submissions

Console