Björne의 창고

잘 알려져 있듯이 곰은 겨울 동안 겨울잠을 잔다. 하지만 적도에서는 겨울에도 어둡고 추워지지 않기 때문에, 아주 오래전에 한 곰 가족이 남쪽으로 이주한 뒤 형성된 곰 공동체의 곰들은 한 해 중 서로 완전히 다른 시기에 겨울잠을 자기 시작했다. Björne는 창고를 열었고 자신이 잠드는 기간에 도둑이 들까 봐 걱정하고 있다. 따라서 고용된 곰 중 항상 누군가가 깨어서 창고를 지킬 수 있도록 다른 곰들을 고용하려 한다.

총 $N$마리의 곰이 이 일자리에 지원했다. 각 곰은 한 해 중 특정한 날에 겨울잠에 들어 정확히 $d$일 동안 연속으로 자며, 이 기간의 어느 날에도 일할 수 없다. Björne가 깨어 있을 때는 자신의 창고를 직접 지킨다고 할 때, Björne가 고용해야 하는 곰의 최소 수는 얼마인가?

매년 $365$일이라고 계산한다(적도에 사는 곰들은 윤년을 신경 쓰지 않는다). 또한 각 달의 일수는 다음과 같다.

• januari는 31일,

• februari는 28일,

• mars는 31일,

• april은 30일,

• maj는 31일,

• juni는 30일,

• juli는 31일,

• augusti는 31일,

• september는 30일,

• oktober는 31일,

• november는 30일이며,

• december는 31일이다.

채점

여러 테스트 케이스 그룹으로 풀이를 채점한다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$30$| $N \leq 15$

$2$ |$40$| $d \leq 182$

$3$ |$30$| 추가 제한 없음.

첫째 줄에 두 정수 $N$와 $d$ ($2 \leq N \leq 10^5, 1 \leq d \leq 364$)가 주어진다. 이는 각각 Björne를 포함한 곰의 수와 각 곰이 잠자는 날의 수이다.

이어지는 $N$개의 줄에는 각 곰이 겨울잠에 드는 날이 주어진다. 날짜는 dd/mm 형식으로 주어진다.

가장 먼저 주어지는 곰은 Björne 자신이다.

Björne가 고용해야 하는 곰의 최소 수를 나타내는 정수 하나를 한 줄에 출력한다.

모든 날에 창고를 지키는 것이 불가능하다면 -1을 출력한다.