"The Price is Right" 게임 쇼에서는 , 4 명의 출연자가 어떤 물건의 가격을 맞추려고 경쟁한다. 승자는 그 물건의 가격을 초과하지 않고 가장 가깝게 맞치는 사람이다.

"Who wants to be a Millionaire" 쇼에서는 , 이와 유사한 일인용 게임 "The Price is Right" 을 도입했다. 이 게임에서는 출연자가 G( 1 <= G <= 30) 번의 가격을 말할 수 있고 , L ( 0 <= L <= 30 ) 번의 생명선을 가진다.

출연자는 실제 가격을 맞추기위해 여러번의 추측을 할 수 있다. 가격을 말할 때 마다 그 가격이 맞는지 , 낮은 가격인지 , 아니면 높은 가격인지를 알려준다. 추측이 맞는다면 출연자가 승리한다. 그렇지 않으면 추측할 수 있는 회수가 감소하고 또한 높은 가격이면 생명선도 감소한다.

출연자는 추측가능한 횟수를 다 사용하던지 혹은 너무 높은 가격을 불러서 남은 생명선이 없으면 지게 된다. 가격은 양의 정수이다.

G 와 L 이 주어질 때 1 에서 N 사이의 어떤 수에서도 출연자가 이기는 전략이 존재하는 최대 N 을 구하는 게 문제이다.

입력

출력

입출력 예

입력

3 0

출력

3

입력

3 1

출력

6

입력

10 5

출력

847

입력

7 7

출력

127

보충 설명

• 먼저 3 을 부르고 3 보다 낮은 가격이면 추측횟수는 2 번 남고 생명선은 없어므로 1 2 로 부르면 되고
• 3 보다 큰 수이면 추측횟수는 2 번 남고 생명선은 1 .... 다시 5 를 부르고 이 보다 낮으면 4 .. 아니면 6

출처:East Central North America 2002