Cut Ribbon · Interview Problem

Back to problems

Codeforces

Easy

Dynamic Programming

Math

Arrays

Cut Ribbon

Maximize the number of pieces you can cut from a ribbon using only allowed lengths.

Acceptance 0%

Start Practice

Problem Statement

You are given a ribbon of length $n$ and three allowed cut lengths $a$ , $b$ , and $c$ .

You may cut the ribbon into any number of pieces, where every piece must have length exactly $a$ , $b$ , or $c$ . Your goal is to use the entire ribbon and maximize the total number of pieces.

Find the maximum possible number of pieces. If it is impossible to cut the ribbon exactly, the answer is $0$.

Key idea

Choose a combination of the three allowed lengths whose total is exactly $n$ , and among all valid combinations, maximize the piece count.

Input Format

A single line contains four integers $n$ , $a$ , $b$ , and $c$ .
The lengths are positive integers.

Output Format

Print one integer: the maximum number of pieces the ribbon can be cut into using only lengths $a$ , $b$ , and $c$ .
Print $0$ if no exact cut is possible.

Constraints

$1 \le n \le 4000$
$1 \le a, b, c \le 4000$

Examples

Sample cases returned by the problem API.

Example 1

Input

5 5 3 2

Output

Explanation

One optimal way is $2 + 3 = 5$ , which gives 2 pieces.

Example 2

Input

7 5 5 2

Output

Explanation

Cut the ribbon as $5 + 2$ . This uses the ribbon exactly and maximizes the number of pieces.

Show 1 more example

Example 3

Input

1 2 3 4

Output

Explanation

No combination of $2 $, \$ 3 $, and \$ 4 $can sum to \$ 1$ exactly.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress