[BOJ] 2839. 설탕 배달

import java.util.Scanner;

public class Main {
	static Scanner sc=new Scanner(System.in);
	static int N=sc.nextInt();
	static int ans=Integer.MAX_VALUE;
	static int memo[]=new int[1668];
	public static void main(String[] args) {	
		for (int i = 0; i < memo.length; i++) {
			memo[i]=Integer.MIN_VALUE;
		}
		go(0,0);
		if(ans==Integer.MAX_VALUE) {
			System.out.println(-1);
		}else {
			System.out.println(ans);
		}
	}
	
	public static void go(int d,int sum) {
		if(d>ans)return;
		if(sum>N)return;
		if(sum==N) {
			if(d<ans) {
				ans=d;
			}
			return;
		}
		if(memo[d]<sum) {
			memo[d]=sum;
		}else {
			return;
		}
		go(d+1,sum+3);
		go(d+1,sum+5);
	}
}