## BIGSEQ - Sequence

no tags

You are given the sequence of all K-digit binary numbers: 0, 1,..., 2K-1. You need to fully partition the sequence into M chunks. Each chunk must be a consecutive subsequence of the original sequence. Let Si (1 ≤ i ≤ M) be the total number of 1's in all numbers in the ith chunk when written in binary, and let S be the maximum of all Si, i.e. the maximum number of 1's in any chunk. Your goal is to minimize S.

### Input

In the first line of input, two numbers, K and M (1 ≤ K ≤ 100, 1 ≤ M ≤ 100, M ≤ 2^K), are given, separated by a single space character.

### Output

In one line of the output, write the minimum S that can be obtained by some split. Write it without leading zeros. The result is not guaranteed to fit in a 64-bit integer.

### Example

```Input:
3 4

Output:
4```

## Code Examples

### #1 Code Example with Python Programming

```Code - Python Programming```

``````pw = [1] * 105
for i in range(1, 105):
pw[i] = pw[i - 1] * 2

def countBits(N, K):
count = 0
for i in range(K):
count += N // pw[i + 1] * pw[i]
count += max(0, N % pw[i + 1] - pw[i] + 1)
return count

def findUpperBound(bitCount, low, high):
middle, best = 0, 0
while low <= high:
middle = (low + high + 1) >> 1
if countBits(middle, K) <= bitCount:
best = middle
low = middle + 1
else:
high = middle - 1
return best

K, M = map(int, raw_input().split())
highestResult = countBits(1 << K, 102) / M + 50
lowestResult = max(1, highestResult - 111)
low, high, best, middle = lowestResult, highestResult, highestResult, 0

while low <= high:
middle = (low + high + 1) >> 1
skippedNumbers, skippedBits = 0, 0
for i in range(M):
if skippedNumbers >= pw[K] - 1:
break
skippedNumbers = findUpperBound(skippedBits + middle, skippedNumbers + 1, pw[K] - 1)
skippedBits = countBits(skippedNumbers, K)
if skippedNumbers >= pw[K]- 1:
best = middle
high = middle - 1
else:
low = middle + 1
print(best)``````
Copy The Code &

Input

cmd
3 4

Output

cmd
4