타노수

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

요약

자릿수가 2^N인 수를 T번 반으로 나눠 한쪽만 남길 때 만들 수 있는 가장 큰 수를 구한다.

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

문제

자릿수가 $2^N$ 인 수 $\displaystyle X = \overline{x\_1 x\_2 x\_3 \dots x\_{2^N}}$ 을 $T$ 번 타노스하여 만들어질 수 있는 가장 큰 수를 출력하라.

자릿수가 $2K$ 인 수 $\displaystyle A = \overline{a\_1a\_2a\_3 \dots a\_{2K}}$ 를 한 번 타노스하면 $\displaystyle \overline{a\_1a\_2 \dots a\_K}$ 혹은 $\displaystyle \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
```