SP2319 BIGSEQ - Sequence

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

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

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.