## COCI '10 Contest 7 #1 Šećer

View as PDF

Points: 3 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem types

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.

#### Input Specification

The first and only line of input contains one integer .

#### Output Specification

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

#### Sample Input 1

4

#### Sample Output 1

-1

#### Sample Input 2

9

#### Sample Output 2

3

#### Sample Input 3

18

#### Sample Output 3

4