C. p-binary
bitmasks; brute force; math
Vasya will fancy any number as long as it is an integer power of two. Petya, on the other hand, is very conservative and only likes a single integer \(p\) (which may be positive, negative, or zero). To combine their tastes, they invented \(p\)-binary numbers of the form \(2^x + p\), where \(x\) is a non-negative integer.For example, some \(-9\)-binary (""minus nine"" binary) numbers are: \(-8\) (minus eight), \(7\) and \(1015\) (\(-8=2^0-9\), \(7=2^4-9\), \(1015=2^{10}-9\)).The boys now use \(p\)-binary numbers to represent everything. They now face a problem: given a positive integer \(n\), what's the smallest number of \(p\)-binary numbers (not necessarily distinct) they need to represent \(n\) as their sum? It may be possible that representation is impossible altogether. Help them solve this problem.For example, if \(p=0\) we can represent \(7\) as \(2^0 + 2^1 + 2^2\).And if \(p=-9\) we can represent \(7\) as one number \((2^4-9)\).Note that negative \(p\)-binary numbers are allowed to be in the sum (see the Notes section for an example).
The only line contains two integers \(n\) and \(p\) (\(1 \leq n \leq 10^9\), \(-1000 \leq p \leq 1000\)).
If it is impossible to represent \(n\) as the sum of any number of \(p\)-binary numbers, print a single integer \(-1\). Otherwise, print the smallest possible number of summands.
\(0\)-binary numbers are just regular binary powers, thus in the first sample case we can represent \(24 = (2^4 + 0) + (2^3 + 0)\).In the second sample case, we can represent \(24 = (2^4 + 1) + (2^2 + 1) + (2^0 + 1)\).In the third sample case, we can represent \(24 = (2^4 - 1) + (2^2 - 1) + (2^2 - 1) + (2^2 - 1)\). Note that repeated summands are allowed.In the fourth sample case, we can represent \(4 = (2^4 - 7) + (2^1 - 7)\). Note that the second summand is negative, which is allowed.In the fifth sample case, no representation is possible.