Description

Mirko needs to deliver $n$ candies to a candy store somewhere.

Mirko can use two types of boxes:

• Type $1$ box, which can hold $3$ candies.
• Type $2$ box, which can hold $5$ candies.

Mirko wants to use as few boxes as possible. For example, if he needs to deliver $18$ candies, he could use $6$ type $1$ boxes. However, the best strategy is to use $3$ type $2$ boxes and $1$ type $1$ box, for a total of $4$ boxes.

Please help Mirko find the minimum number of boxes needed.

Input Format

The input has one line.

The first line contains a positive integer $n$, representing the number of candies.

Output Format

The output has one line.

The first line contains a positive integer, the minimum number of boxes needed. If it is impossible to deliver $n$ candies using these $2$ types of boxes, output -1.

4

-1

9

3

18

4

Hint

Constraints

For $100\%$ of the testdata, $3 \le n \le 5000$.

Notes

This problem is worth $30$ points.

Translated from COCI2010-2011 CONTEST #7 T1 ŠEĆER.

Translated by ChatGPT 5