#P6702. [COCI2010-2011#7] ŠEĆER

[COCI2010-2011#7] ŠEĆER

题目背景

Mirko 在制糖厂当送货员。

题目描述

Mirko 需要向某地的一家糖果店运送 nn 颗糖。

Mirko 可以使用两种类型的包装盒子:

  • 一种是可以装 33 颗糖的 11 号包装;
  • 另一种是可以装 55 颗糖的 22 号包装。

Mirko 想让包装盒尽可能少。例如,他要运送 1818 颗糖,则可以使用 6611 号包装。但是,最优策略是 3322 号包装和 1111 号包装。这样总共有 44 个包装。

请你帮助 Mirko 找到需要包装盒最少的方案。

输入格式

输入数据共一行。

第一行一个正整数 nn,表示糖果颗数。

输出格式

输出数据共一行。

第一行,一个正整数表示需要包装盒最少的方案数的包装盒数,如果不可能用这 22 种包装盒运 nn 颗糖,输出 -1

4

-1
9

3
18

4

提示

数据规模及约定

对于 100%100\% 的数据,3n50003 \le n \le 5000

说明

本题满分 3030 分。

译自 COCI2010-2011 CONTEST #7 T1 ŠEĆER