Technocup 2020 - Elimination Round 2 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

brute force

math

*1600

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. p-binary

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputVasya 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).

Input

The only line contains two integers $$$n$$$ and $$$p$$$ ($$$1 \leq n \leq 10^9$$$, $$$-1000 \leq p \leq 1000$$$).

Output

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.

Examples

Input

24 0

Output

2

Input

24 1

Output

3

Input

24 -1

Output

4

Input

4 -7

Output

2

Input

1 1

Output

-1

Note

$$$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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/05/2024 04:15:55 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|