P17188 [ICPC 2017 Hong Kong R] Sets

For a fixed number $n$, we define $S_1$ as the set of integers $1, 2, \dots, n$. And for any $i > 1$, we define $S_i$ as a set containing all sums of two different numbers in $S_{i-1}$. For example, if $n = 3$, we have $$ \begin{matrix} S_1 & = &\{1,2,3\},\\ S_2 & = &\{3,4,5\},\\ S_3 & = &\{7,8,9\},\\ S_4 & = &\{15, 16, 17\}.\\ \end{matrix} $$ Then, we sort each set respectively, and combine them in order into a sequence $L$. In the above case, we have the sequence $L = 1, 2, 3, 3, 4, 5, 7, 8, 9, 15, 16, 17, \dots$. Now, given integers $n$ and $k$, what is the $k$-th number in sequence $L$?

The input file contains several test cases, please handle it to the end of file. For each case, there is only one line containing two integers $n$ and $k$ ($n \le 1000, k \le 10^{1000}$). When $n = 3$, the input satisfies that $k \leq 100000$.

For each case, output one integer indicating the $k$-th number of the sequence. Output $-1$ if it does not exist.