KUSAC - Kusac

no tags 

Mirko has given up on the difficult coach job and switched to food tasting instead. Having skipped breakfast like a professional connoisseur, he is visiting a Croatian cured meat festival. The most renowned cook at the festival, Marijan Bajs, has prepared N equal sausages which need to be distributed to M tasters such that each taster gets a precisely equal amount. He will use his trusted knife to cut them into pieces.

In order to elegantly divide the sausages, the number of cuts splitting individual sausages must be as small as possible. For instance, if there are two sausages and six tasters (the first test case below), it is sufficient to split each sausage into three equal parts, making a total of four cuts. On the other hand, if there are three sausages and four tasters (the second test case below), one possibility is cutting off three quarters of each sausage. Those larger parts will each go to one of the tasters, while the fourth taster will get the three smaller pieces (quarters) left over.

Mirko wants to try the famous sausages, so he volunteered to help Bajs. Help them calculate the minimum total number of cuts needed to carry out the desired division.

Input

The first and only line of input contains two positive integers, N and M (1 ≤ N, M ≤ 100), the number of sausages and tasters, respectively.

Output

The first and only line of output must contain the required minimum number of cuts.

Example

Input:
2 6

Output:
4
Input:
3 4

Output:
3
Input:
6 2

Output:
0

hide comments
kaleoum: 2020-01-29 09:53:05

e n=55&m=79
ans 78

smso: 2019-04-07 06:53:31

play with some test cases and use a recursive function

Wumbolo: 2016-07-08 06:31:31

there is a very simple closed formula :) Input Constraints are waaay too low

chhavipatel: 2016-01-25 21:15:45

can anyone provide some tricky test cases (n and m >50)

Last edit: 2016-01-25 22:05:49
Anuj Agrawal: 2015-05-14 19:47:06

Can anybody provide the ans for test case n=55&m=79.

Petar Bosnjak: 2014-06-26 14:07:55

This problem is ok now , everyone who got WA or TLE can send their solutions again
--Francky--> (2) You have to make a rejudge, and explain why the last rejudge was cancelled. Thanks.

Last edit: 2014-06-26 16:09:22
Francky: 2014-06-18 08:28:47

It seems rejudged had been cancelled. Can you explain what happened ?

Tomislav Babic: 2014-06-17 13:17:04

@Francky
127 people got AC with wrong files because error was in only one test case which is not even official. Input in that test case was 0 and output 0. All other test cases were correct.
--Francky--> Many thanks.

Last edit: 2014-06-17 15:26:16
Tomislav Babic: 2014-06-17 13:13:59

Test cases problem solved! All solution are rejudged.

Tomislav Babic: 2014-06-17 12:38:00

@Francky I have uploaded official solution and indeed there is something wrong with test cases. I will disable testing until I solve the test cases problem and then I will reevaluate everything!
Sorry for the inconvenience!
--ans(Francky)--> Many thanks for that.
Please explain how 127 people got AC with wrong files !!??!! Did you change things recently ?

Last edit: 2014-05-18 16:50:47

Added by:Tomislav Babic
Date:2013-10-05
Time limit:0.109s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:COCI 2013 1. round