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

Copy

Sample Output 1

Copy

-1

Sample Input 2

Copy

Sample Output 2

Copy

Sample Input 3

Copy

Sample Output 3

Copy

Comments

1

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

reminds me a lot about the CCCS2 from 2022