Room Assignment

Interview

Time limit2sMemory limit512 MB

Summary

Count students by grade and gender, then combine grades 1-2 into one pool and split grades 3-6 by gender, computing rooms as ceil(count/K).

Level: Easy3 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

An elementary school is going on a three day field trip. Every student from grade 1 to grade 6 needs a room, and the rules are these.

Grades 1 and 2 share a room with no separation by gender and no separation by grade.
Grades 3 and 4 share a room with no separation by grade, but boys stay with boys and girls stay with girls.
Grades 5 and 6 follow the same rule as grades 3 and 4.
A room may hold a single student.

Given the largest number of students $K$ that one room holds, write a program that finds the minimum number of rooms needed to place every student under these rules.

For example, if the students on the trip are counted as below and $K = 2$ , then 9 rooms are needed.

Grade	Girls	Boys
Grade 1	1	2
Grade 2	2	1
Grade 3	1	3
Grade 4	0	1
Grade 5	1	2
Grade 6	1	1

Input

The first line has the number of students on the trip $N$ ( $1 \le N \le 1{,}000$ ) and the largest number of students one room holds $K$ ( $1 \le K \le 1{,}000$ ), separated by a space.

Each of the next $N$ lines has the gender $S$ and the grade $Y$ ( $1 \le Y \le 6$ ) of one student, separated by a space. $S$ is 0 for a girl and 1 for a boy.

Output

Print the minimum number of rooms needed to place every student, on one line.

Examples4

Example 1
Input
```
3 3
0 3
1 5
0 6
```
Expected output
```
3
```

Example 2

Input

Expected output

Example 3
Input
```
1 1
0 1
```
Expected output
```
1
```
Example 4
Input
```
1 1000
1 6
```
Expected output
```
1
```