타노수

시간 제한1초메모리 제한1024 MB

요약

2^N자리 수가 주어질 때, 매번 왼쪽 또는 오른쪽 절반을 남기는 방식으로 T번 스냅한 뒤 얻을 수 있는 가장 큰 수를 구합니다.

난이도: 보통10점 중 6점
유형: 분할 정복, 문자열, 문자열 매칭
정답자: 아직 제출이 없습니다

문제

자릿수가 $2^N$ 인 수 $X = \overline{x_1 x_2 x_3 \dots x_{2^N}}$ 을 $T$ 번 타노스하여 만들어질 수 있는 가장 큰 수를 출력하라.

자릿수가 $2K$ 인 수 $A = \overline{a_1 a_2 a_3 \dots a_{2K}}$ 를 한 번 타노스하면 $\overline{a_1 a_2 \dots a_K}$ 또는 $\overline{a_{K+1} a_{K+2} \dots a_{2K}}$ 중 하나가 된다.

입력

첫 번째 줄에 $N$ 과 $T$ 가 공백으로 구분되어 주어진다.

두 번째 줄에 자릿수가 $2^N$ 인 수 $X$ 가 주어진다.

출력

첫 번째 줄에 자릿수가 $2^N$ 인 수를 $T$ 번 타노스하여 만들어질 수 있는 가장 큰 수를 출력한다.

제한

$1 \le N \le 20$
$1 \le T \le N$
$1 \le x_i \le 9$

예제2

예제 1
입력
```
3 2
57834561
```
예상 출력
```
83
```
예제 2
입력
```
2 2
2438
```
예상 출력
```
8
```