【codeforce】A. Potion of Immortality

A. Potion of Immortality

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

The world famous scientist Innokentiy has just synthesized the potion of immortality. Unfortunately, he put the flask with this potion on the shelf where most dangerous poisons of all time were kept. Now there are n flasks on this shelf, and the scientist has no idea which of them contains the potion of immortality.

Fortunately, Innokentiy has an infinite amount of rabbits. But the scientist doesn't know how exactly these potions affect rabbits. There is the only thing he knows for sure. If rabbit tastes exactly k potions from the flasks on the shelf, it will survive if there was the immortality potion among them and die otherwise. If rabbit tastes the number of potions different from k, the result will be absolutely unpredictable, so the scientist won't make such experiments no matter what.

The scientist intends to minimize the amount of lost rabbits while searching for the potion of immortality. You should determine how many rabbits he has to sacrifice in the worst case.

Input

The only line contains two integers separated by space — n and k (1 ≤ n ≤ 2000, 1 ≤ k ≤ n) — the number of flasks on the Innokentiy's shelf and the number of potions Innokentiy will give to a single rabbit to taste.

Output

If the scientist cannot determine which flusk contains the potion of immortality, output «-1». Otherwise, output a single integer — the minimal number of rabbits that Innokentiy will sacrifice in the worst case while searching for the potion of immortality.

Examples

Input

3 2

Output

1

Input

4 2

Output

2

题意：有n个瓶子，只有一瓶没毒，一个兔子可以一次喝k瓶，问在最糟糕的情况下，最少牺牲几只兔子

题解：如果n=1,k=1;肯定没毒，不用试，结果为0

如果n!=1,k=1,最糟情况则需要试毒n-1次

如果n,k,都不为1，n/k次是必须要试的，m=n%k,剩下的如果是0或者1，不需要再试了，否则要再试一次

code：

#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
	int n,k;
	while(~scanf("%d%d",&n,&k)){
	int m=n/k;
	if(n==k&&n!=1) printf("-1\n");
	else{
		if(k==1) printf("%d\n",n-1);
		else{
			if(n%k==1||n%k==0) printf("%d\n",m);
			else printf("%d\n",m+1);
		}
	}
	}
	return 0;
 }