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

• 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.