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