C. p

C. p

链接：

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 pp (which may be positive, negative, or zero). To combine their tastes, they invented pp-binary numbers of the form 2x+p2x+p, where xxis a non-negative integer.

For example, some −9−9-binary ("minus nine" binary) numbers are: −8−8 (minus eight), 77 and 10151015 (−8=20−9−8=20−9, 7=24−97=24−9, 1015=210−91015=210−9).

The boys now use pp-binary numbers to represent everything. They now face a problem: given a positive integer nn, what's the smallest number of pp-binary numbers (not necessarily distinct) they need to represent nn as their sum? It may be possible that representation is impossible altogether. Help them solve this problem.

For example, if p=0p=0 we can represent 77 as 20+21+2220+21+22.

And if p=−9p=−9 we can represent 77 as one number (24−9)(24−9).

Note that negative pp-binary numbers are allowed to be in the sum (see the Notes section for an example).

Input

The only line contains two integers nn and pp (1≤n≤1091≤n≤109, −1000≤p≤1000−1000≤p≤1000).

Output

If it is impossible to represent nn as the sum of any number of pp-binary numbers, print a single integer −1−1. Otherwise, print the smallest possible number of summands.

Examples

input

Copy

24 0

output

Copy

2

input

Copy

24 1

output

Copy

3

input

Copy

24 -1

output

Copy

4

input

Copy

4 -7

output

Copy

2

input

Copy

1 1

output

Copy

-1

Note

00-binary numbers are just regular binary powers, thus in the first sample case we can represent 24=(24+0)+(23+0)24=(24+0)+(23+0).

In the second sample case, we can represent 24=(24+1)+(22+1)+(20+1)24=(24+1)+(22+1)+(20+1).

In the third sample case, we can represent 24=(24−1)+(22−1)+(22−1)+(22−1)24=(24−1)+(22−1)+(22−1)+(22−1). Note that repeated summands are allowed.

In the fourth sample case, we can represent 4=(24−7)+(21−7)4=(24−7)+(21−7). Note that the second summand is negative, which is allowed.

In the fifth sample case, no representation is possible.

题解：首先我们先判断是不是存粹求二进制，如果是就很简单，不是就枚举要减去的个数，并且判断此时的二进制数1的个数s，这个s是最少的个数，最大个数是全是1所以最大个数即那个数，那么只要枚举的数在这个范围内就行

代码：

#include<bits/stdc++.h>
using namespace std;
int n,t,m,k,d,s;
int main()
{scanf("%d %d",&n,&m);s=0;if(m==n)cout<<-1;else if(m==0){while(n){n=n&(n-1);s++;}printf("%d",s);}else{for(int i=1;i<=1000;i++){int k=n-i*m;int p=k;s=0;while(k){k=k&(k-1);s++;}if(s<=i&&i<=p){printf("%d",i);return 0;}}printf("-1");}
}