The Bottle Merging Problem

CC bought \(N\) bottles, each with an infinite capacity, and initially each bottle contains 1 liter of water. Realizing that he has too many bottles, CC has decided to reduce the number of bottles to at most \(K\). He can perform the following operation any number of times: choose two bottles that currently contain the same amount of water (say \(a\) liters), then pour all the water from one bottle into the other so that the receiving bottle now contains \(2a\) liters, and discard the empty bottle. Note that he cannot discard a bottle unless it is empty.

However, there are cases where it is impossible to obtain at most \(K\) bottles by merging the existing ones. In such cases, CC may buy additional new bottles (each new bottle also starts with 1 liter of water) until it becomes possible to merge them all and have \(K\) or fewer bottles in the end.

It can be observed that after optimally merging the bottles, the number of bottles will equal the number of 1's in the binary representation of the total amount of water \(S = N + x\), where \(x\) is the number of new bottles purchased. Thus, the goal is to find the minimum \(x\) for which

[ \text{popcount}(N+x) \le K, ]

where \(\text{popcount}(\cdot)\) is the number of ones in the binary representation of the number.

For example, if \(N=3\) and \(K=1\), then initially the three bottles yield \(3 = 11_2\) (two 1's). Merging is not enough, so by buying one new bottle, \(3+1=4\) which is \(100_2\) (one 1), meeting the requirement \(\le 1\). Hence, the answer is 1.

inputFormat

The input consists of two integers \(N\) and \(K\) separated by a space, where \(N\) is the initial number of bottles and \(K\) is the maximum allowed bottles after merging.

outputFormat

Output a single integer: the minimum number of new bottles CC must buy so that, after a series of merging operations, the total number of bottles is at most \(K\).

sample

3 1

1