Under construction

Still being built. Things may change

Sugar Delivery

Interview

Time limit1sMemory limit128 MB

Summary
Find the minimum number of 3kg and 5kg bags that sum to exactly N kilograms, or -1 if impossible.
Level

Easy2 of 10

Topics
Greedy, Math
Solved
No attempts yet

Problem

Sanggeun delivers sugar from a sugar factory to a candy store. This time, he must deliver exactly N kilograms of sugar.

The sugar is available only in 3-kilogram bags and 5-kilogram bags. Sanggeun wants to carry as few bags as possible.

Find the minimum number of bags needed to make exactly N kilograms. If it is impossible, output -1.

Input

The first line contains an integer N.

3 <= N <= 5000

Output

Print the minimum number of bags needed to deliver exactly N kilograms.

If it is impossible to make exactly that amount, print -1.

Examples5

  1. Example 1

    Input
    18
    Expected output
    4

  2. Example 2

    Input
    4
    Expected output
    -1

  3. Example 3

    Input
    6
    Expected output
    2

  4. Example 4

    Input
    9
    Expected output
    3

  5. Example 5

    Input
    11
    Expected output
    3