886. Allocate Bus Seats

0

Medium

A bus has n rows of seats, numbered from 1 to n, with ten seats in each row, labeled from 1 to 10.
Given a list of reservedSeats indicating the seats already reserved, where reservedSeats[i] = [row, seat] represents a reserved seat in row 'row' and labeled with 'seat', determine the maximum number of four-person groups that can be assigned on the bus seats. A four-person group occupies four adjacent seats in a single row. Seats across an aisle (such as [row, seat] and [row, seat+1]) are not considered adjacent, except in the case where an aisle splits a four-person group in the middle, with two people on each side.
Return the maximum number of four-person groups that can be assigned on the bus seats.

Input Format

The first line of the input contains two integers, n and m, representing the number of rows and the number of reserved seats, respectively.
The following m lines each contain two integers, i and j, indicating that the seat in row 'i' and labeled with 'j' is already reserved.

Output Format

Return a single integer representing the maximum number of four-person groups that can be assigned 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