Sugar Delivery 2

Interview

Time limit0.25sMemory limit1024 MB

Summary

Find the fewest 3-kg and 5-kg bags that add up to exactly N kilograms, or report -1 if no combination works.

Level: Easy3 of 10
Topics: Math, Greedy
Solved: No attempts yet

Problem

Sanggeun delivers sugar from a sugar factory these days. He must deliver exactly $N$ kilograms of sugar to a candy shop. The factory packs its sugar in bags. There are 3-kilogram bags and 5-kilogram bags.

Sanggeun is lazy, so he wants to carry as few bags as possible. For example, when he must deliver 18 kilograms of sugar, he could take six 3-kilogram bags. If he delivers three 5-kilogram bags and one 3-kilogram bag instead, he can deliver with fewer bags.

Input

The first line contains $N$ . ( $3 \leq N \leq 10^{18}$ )

Output

Print the minimum number of bags Sanggeun delivers. If it is impossible to deliver exactly $N$ kilograms, print -1.

Examples5

Example 1
Input
```
18
```
Expected output
```
4
```
Example 2
Input
```
4
```
Expected output
```
-1
```
Example 3
Input
```
6
```
Expected output
```
2
```
Example 4
Input
```
9
```
Expected output
```
3
```
Example 5
Input
```
11
```
Expected output
```
3
```