COCI '10 Contest 7 #1 Šećer

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 $N$ ~N~ kilograms of sugar to a candy store on the Adriatic coast. Mirko can use two types of packages, the ones that contain $3$ ~3~ kilograms, and the ones with $5$ ~5~ kilograms of sugar.

Mirko would like to take as few packages as possible. For example, if he has to deliver $18$ ~18~ kilograms of sugar, he could use six $3$ ~3~-kilogram packages. But, it would be better to use three $5$ ~5~-kilogram packages, and one $3$ ~3~-kilogram package, resulting in the total of four packages.

Help Mirko by finding the minimum number of packages required to transport exactly $N$ ~N~ kilograms of sugar.

Input Specification

The first and only line of input contains one integer $N$ ~N~ $(3 \leq N \leq 5\,000)$ ~(3 \leq N \leq 5\,000)~.

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 $N$ ~N~ kilograms, output -1.

Sample Input 1

Sample Output 1

-1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Comments

0

Zanger commented on March 11, 2022, 12:56 a.m.

reminds me a lot about the CCCS2 from 2022