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