P6702 [COCI 2010/2011 #7] ŠEĆER

Mirko works as a delivery person in a sugar factory.

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.

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

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

#### Constraints For $100\%$ of the testdata, $3 \le n \le 5000$. #### Notes This problem is worth $30$ points. Translated from [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #7](https://hsin.hr/coci/archive/2010_2011/contest7_tasks.pdf) T1 ŠEĆER. Translated by ChatGPT 5