Nhân là một sinh viên vừa mới nhập học vào một trường Đại học danh tiếng. Tuy nhiên, gia đình cậu ấy có nhiều khó khăn nên Nhân Quyết định tự nấu cơm để ăn. Đầu tháng, Nhân thường về nhà để mang gạo lên trường, cậu ta được mẹ đưa cho 2 loại xô, một loại 3 kg và 1 loại 5kg. Nhân sẽ phải đong đủ số gạo cần thiết để mang lên chỗ học bằng 2 loại xô trên.

Ví dụ: Nhân cần mang lên 18kg gạo, thì cậu sẽ phải đong bằng 3 xô 5kg + 1 xô 3 kg, hoặc 6 xô 3kg.

Yêu cầu: Là một lập trình viên, đồng chí hãy giúp anh ấy đong số gạo cần thiết với yêu cầu sử dụng số lần đong ít nhất có thể, nếu không thể đong được, hãy in ra giá trị -1.

Dữ liệu vào: Vào từ thiết bị chuẩn một dòng duy nhất N, là số gạo cần thiết để Nhân mang lên chỗ học (0 < N < 5000)

Kết quả: In ra thiết bị chuẩn là đáp án của bài toán

Ví dụ:

Dữ liệu vào

21

Kết quả

5

Giải thích

Sử dụng 3 xô 5kg và 2 xô 3kg

Ràng buộc:

• Có 20% số test tương ứng với 20 điểm có 1 ≤ N ≤ 50;
• Có 20% số test tương ứng với 20 điểm có 10 ≤ N ≤ 100;
• Có 20% số test tương ứng với 20 điểm có 50 ≤ N ≤ 500;
• Có 20% số test tương ứng với 20 điểm có 100 ≤ N ≤ 1000;
• Có 20% số test tương ứng với 20 điểm có 200 ≤ N ≤ 5000.