흥정할까 말까

NZPC 엔터테인먼트 사업부가 새 TV 게임쇼 "흥정할까 말까"를 기획했다. 이 쇼에는 여러 개의 서류가방이 있고, 각 가방 안에는 정해진 상금이 적힌 수표가 한 장씩 들어 있다. 상금 목록(가방 하나당 하나)은 미리 공개되지만, 어떤 가방에 어떤 상금이 들어 있는지는 아무도 모른다. 참가자 한 명이 내용물을 모른 채 가방 하나를 받는다.

게임은 여러 라운드로 진행된다. 매 라운드(첫 라운드 포함)마다 NZPC 은행이 먼저 참가자에게 일정 금액을 제안한다. 참가자는 이 제안을 받아들여 즉시 게임을 그만둘 수 있으며, 이때는 자기 가방의 내용물을 포기한다. 제안을 거절하면, 아직 열지 않은 가방 중 하나를 열어 그 상금을 공개하고, 그 상금이 자기 가방에 들어 있을 가능성을 제거한다. 참가자가 제안을 받아들이거나, 참가자의 가방을 제외한 모든 가방이 열릴 때까지 게임이 계속된다. 후자의 경우 참가자의 가방을 열어 그 안의 수표를 가지고 집으로 돌아간다.

게임 세부 규칙:

• 남은 상금들의 합을 $S$, 남은 상금의 개수를 $N$이라 하자. 은행의 제안 금액은 항상 $S / N^2$이다.
• 각 가방은 남은 상금 각각을 담고 있을 확률이 모두 같다.
• 참가자는 $u(x)$의 기댓값을 최대화하도록 최적으로 플레이한다. 여기서 $u(x) = \ln(x)$는 $x$달러를 받았을 때의 효용(자연로그)이다. 이 오목한 효용 함수는, 이미 많은 돈을 가지고 있을수록 같은 금액이 늘어나는 것의 가치가 더 작아진다는 사실을 반영한다.

상금 값의 집합이 주어질 때, 최적으로 플레이하는 참가자가 평균적으로 상금 $M$달러보다 많이 받게 되는지 판정하라. 최적 전략은 기대 효용을 최대화하며, $M$과 비교하는 값은 그 전략을 따랐을 때의 기대 상금(달러)이다.

입력은 여러 개의 게임 시나리오로 이루어진다. 각 시나리오는 두 줄로 주어진다. 첫 줄에는 상금들의 달러 값이 공백 하나로 구분되어 나열되며, 모든 상금 값은 양의 정수이다. 둘째 줄에는 양의 정수 $M$ 하나가 주어지는데, 이는 NZPC가 감당할 수 있는, 최적 플레이 하에서의 게임당 기대 상금의 최댓값이다. 각 시나리오의 상금은 최대 25개이며, 값이 중복될 수 있다.

각 게임 시나리오에 대해, 최적 플레이 하에서의 게임당 기대 상금이 $M$보다 크면 UNACCEPTABLE을, 그렇지 않으면 OK를 한 줄에 하나씩 출력하라. 입력은 -1만 적힌 줄로 끝나며, 이 줄은 처리하지 않는다.