#6959. A. 切割绸带(Cut Ribbon)

A. 切割绸带(Cut Ribbon)

A. 切割绸带(Cut Ribbon)

**时间限制:**1 秒
**内存限制:**256 MB

题目描述

Polycarpus 有一条长度为 (n) 的绸带。他想把绸带切成若干段,并满足以下条件:

  • 每段的长度必须是 (a)、(b)、(c) 中的一个。
  • 在满足上述条件的前提下,切出的段数尽可能多。

请帮助 Polycarpus 求出最多能切出多少段。

输入格式

一行包含四个整数 (n,a,b,c),分别表示原绸带的长度,以及切割后每段允许的三种长度。

这三个允许长度可能相同。

输出格式

输出一个整数,表示最多能切出的段数。

保证至少存在一种符合条件的切割方案。

数据范围

1≤n,a,b,c≤40001 \le n,a,b,c \le 4000

样例 1

输入

5 5 3 2

输出

2

说明

可以切成长度分别为 (2) 和 (3) 的两段。

样例 2

输入

7 5 5 2

输出

2

说明

可以切成长度分别为 (5) 和 (2) 的两段。

测试点编号 层级 n a, b, c 特殊性质 标准输出 设计目的
1 弱数据 1 1, 1, 1 最小规模、三种长度相同 1 检查初始化和最小可达状态
2 7 5, 2, 5 长度重复、必须精确拼接 2 检查重复长度及不能把剩余长度忽略
3 边界数据 4, 5, 6 无法恰好拼出 -1000000000 检查不可达状态;这是当前代码的实际输出
4 正常数据 20 3, 5, 7 多种可行组合 6 检查在精确拼接的前提下最大化段数
5 极限数据 4000 17, 23, 31 大规模、复杂精确组合 232 检查完整 DP 范围及较复杂的最优组合