Hide

Problem D
Raðir

Languages en is
/problems/radir/file/statement/en/img-0001.jpg
Three of Hearts by Harry Shelton, Unsplash
You really like playing card games with your friend. She recently introduced you to a new card game. Initially $p$ cards are dealt to both players. You then take turns drawing a card to your hand and then discarding a card from your hand. The goal is to obtain a sequence in your hand. A sequence is any three cards of the same suite, such that if the card of the smallest value has value $a$, then the other two cards have value $a+1$ and $a+2$. You can declare victory at the end of your turn, as long as you have a sequence in your hand.

You just lost a game to your friend. This does not bother you too much, since you just learned how to play the game, but you want to learn from your mistakes. Looking over your cards, you wonder how early you could have achieved a sequence, had you played optimally.

Input

The first line of the input contains two integers $n$, the total number of cards, and $p$, the number of cards you can keep in your hand, where $3 \leq p \leq n \leq 10^6$. Then there are $n$ lines, the $j$-th of which contains two integers $c_ j$ and $k_ j$, the suit and value of the $j$-th card you receive, where $1 \leq c_ j \leq 4$ and $1 \leq k_ j \leq 13$. The first $p$ cards are the cards you got dealt initially, and the subsequent $n-p$ cards are the cards you drew, in that order.

Output

The output should contain one integer, the fewest number of turns it could have taken you to obtain a sequence. If no sequence can be optained, output “Neibb”.

Scoring

Group

Points

Constraints

1

27

$n \leq 100$

2

23

$n \leq 5\, 000$

3

15

$n \leq 10^6$, all cards have the same suit and each card has a value of $1$, $2$ or $3$

4

35

No further constraints

Sample Input 1 Sample Output 1
5 3
1 1
1 2
4 3
2 3
1 3
2
Sample Input 2 Sample Output 2
5 3
1 1
1 2
1 4
1 3
1 5
1
Sample Input 3 Sample Output 3
5 3
1 1
1 2
1 4
1 5
1 7
Neibb

Please log in to submit a solution to this problem

Log in