미제르

Préférence는 동유럽에서 매우 인기 있는 카드 게임이다. 보통 32장짜리 덱으로 하며, 이 덱은 무늬 네 가지(스페이드, 클럽, 다이아몬드, 하트)마다 7부터 10까지의 숫자 카드와 잭, 퀸, 킹, 에이스로 이루어진다. 한 라운드에서 세 명의 플레이어가 각각 10장씩 받고, 두 장은 탈론으로 테이블에 놓인다. 그다음 플레이어들이 비드를 하는 경매 단계가 온다. 비드는 최소 몇 번의 트릭을 따겠다는 의무다. 특수한 비드인 미제르는 다른 플레이어가 어떻게 플레이하든 트릭을 하나도 따지 않겠다는 의무다.

이 문제는 $A \times B$장의 카드로 이루어진 덱을 쓰는 프리페랑스 변형을 다룬다. 여기서 $A$는 무늬의 수, $B$는 무늬마다 있는 랭크의 수다. 표준 32장 덱은 $A = 4$, $B = 8$이다. 무늬는 1부터 $A$까지, 랭크는 1부터 $B$까지 번호를 붙인다.

미제르가 보장된다는 것은, 무늬마다 손패에 있는 그 무늬의 카드를 랭크 순으로 $b_1 < b_2 < \cdots < b_k$라고 정렬했을 때($k$는 손패에 있는 그 무늬 카드의 수) 모든 $i$($1 \le i \le k$)에 대해 $b_i \le 2i - 1$이 성립한다는 뜻이다. 어떤 무늬의 카드가 손패에 없으면($k = 0$) 이 조건은 자명하게 성립한다.

손패에는 $n$장의 카드가 있다. 가지고 있지 않은 카드 중에서 원하는 $x$장을 골라 손패에 추가할 수 있다. 그다음 손패의 $n + x$장 중 $x$장을 반드시 골라 버려서, 손패에 $n$장이 남도록 해야 한다. 보장된 미제르가 되도록 손패를 바꿀 수 있는 $x$의 최솟값을 구하라.