연속 패

Three of Hearts, Harry Shelton 촬영, Unsplash

당신은 친구와 카드 놀이를 하는 것을 무척 좋아하는데, 친구가 최근 새로운 게임을 알려 주었다. 먼저 각 플레이어는 손에 들고 있을 카드 $p$장을 받는다. 그다음 번갈아 가며 차례를 진행하며, 자기 차례인 플레이어는 카드 한 장을 뽑아 손에 넣은 뒤 손에서 카드 한 장을 버린다(방금 뽑은 카드일 수도 있다). 게임의 목표는 손에 연속 패를 만드는 것이다. 연속 패는 같은 무늬의 카드 세 장으로 이루어지며, 가장 작은 카드의 값이 $a$라면 나머지 두 카드의 값은 $a+1$와 $a+2$여야 한다. 자신의 차례가 끝났을 때 손에 적어도 하나의 연속 패가 있다면 승리를 선언할 수 있다.

당신은 방금 친구에게 졌다. 이제 막 이 게임을 배우기 시작했으므로 크게 실망하지는 않았지만, 그래도 자신의 실수에서 배우고 싶다. 당신은 자신의 카드들을 보며, 최선의 방법으로 플레이했다면 얼마나 일찍 연속 패를 만들 수 있었을지 궁금해한다.

채점

그룹 | 점수 | 제한

1 | 27 | $n \leq 100$

2 | 23 | $n \leq 5\,000$

3 | 15 | $n \leq 10^6$, 모든 카드는 같은 무늬이며 값은 $1$, $2$ 또는 $3$이다

4 | 35 | 추가 제한 없음

첫 번째 줄에는 카드의 총개수와 손에 들 수 있는 카드의 개수를 나타내는 두 정수 $n$와 $p$가 주어진다 ($3 \leq p \leq n \leq 10^6$). 이어서 $n$개의 줄이 주어지며, $j$번째 줄에는 특정 카드의 무늬와 값을 나타내는 두 정수 $c_j$와 $k_j$가 주어진다 ($1 \leq c_j \leq 4$, $1 \leq k_j \leq 13$). 처음 $p$장의 카드는 처음에 손에 들고 있던 카드들이며, 이후 $n-p$장의 카드는 뽑은 순서대로 나열된 카드들이다.

최선의 방법으로 플레이했을 때 연속 패를 만드는 데 걸릴 수 있었던 최소 차례 수를 나타내는 정수 하나를 출력한다. 연속 패를 만들 방법이 없다면 ```Neibb`''을 출력한다.