Problem Background

Mirko works as a deliveryman at a sugar factory.

Problem Description

Mirko needs to deliver \( n \) pieces of candy to a candy store.

Mirko can use two types of packaging boxes:
- One type can hold 3 pieces of candy (Type 1 packaging).
- The other type can hold 5 pieces of candy (Type 2 packaging).

Mirko wants to use as few packaging boxes as possible. For example, if he needs to deliver 18 pieces of candy, he could use 6 Type 1 packaging boxes. However, the optimal strategy is 3 Type 2 packaging boxes and 1 Type 1 packaging box, totaling 4 packaging boxes.

Help Mirko find the plan with the fewest packaging boxes.

Input Format

The input consists of a single line.

The first line contains a positive integer \( n \), representing the number of pieces of candy.

Output Format

The output consists of a single line.

The first line contains a positive integer representing the minimum number of packaging boxes needed. If it is not possible to deliver \( n \) pieces of candy using these two types of packaging boxes, output -1.

Sample Input and Output

Sample Input #1

4

Sample Output #1

-1

Sample Input #2

9

Sample Output #2

3

Sample Input #3

18

Sample Output #3

4

Notes

Data Size and Constraints

For 100% of the data, \( 3 \le n \le 5000 \).

Notes

This problem is worth 30 points.

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

见题面 Input 部分

见题面 Output 部分