Mirko works in a sugar factory as a delivery boy. He has just received an order: he has to deliver exactly kilograms of sugar to a candy store on the Adriatic coast. Mirko can use two types of packages, the ones that contain kilograms, and the ones with kilograms of sugar.
Mirko would like to take as few packages as possible. For example, if he has to deliver kilograms of sugar, he could use six -kilogram packages. But, it would be better to use three -kilogram packages, and one -kilogram package, resulting in the total of four packages.
Help Mirko by finding the minimum number of packages required to transport exactly kilograms of sugar.
The first and only line of input contains one integer .
The first and only line of output should contain the minimum number of packages Mirko has to use. If it is impossible to deliver exactly kilograms, output
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
Sample Input 3
Sample Output 3
reminds me a lot about the CCCS2 from 2022