 New update is available. Click here to update.
Last Updated: 28 Feb, 2021
##### Cut Into Segments
Moderate
Problem statement #### You are given an integer ‘N’ denoting the length of the rod. You need to determine the maximum number of segments you can make of this rod provided that each segment should be of the length 'X', 'Y', or 'Z'.

##### Input Format:
``````The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘T’ lines represent the ‘T’ test cases.

The only line of each test case contains 4 integers denoting ‘N’, ’X’, ’Y’, and ‘Z’,  where ‘N’ is the length of the rod and 'X', 'Y', 'Z' are the segments into which a given rod can be cut into.
``````
##### Output Format:
``````For each test case, return the maximum number of cut segments from the given rod.

Print the output of each test case in a separate line.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraint:
``````1 <= T <= 50
1 <= N <= 10000
1 <= X, Y, Z <= N

Time Limit: 1 sec
`````` Approaches

## 01Approach The key idea is that no maximum cuts that can be made in the rod of length ‘N’ depend upon Maximum cuts made in shorter length.For ‘n’ length rod ans depends upon 'N’ - ’X’, ’N’ - ’Y’ and ‘N’ - ’Z’ sizes of the rod.

Algorithm:

1. Create two base case for recursive function such that if length of rod is 0, then return 0. Also add the case if length of rod is less than 0 return infinity.
2. Recursively call the function on ‘N’ - ’X’, ’N’ - ’Y’ and ‘N’ - ’Z’ length rods.
3. The answer for ‘N’ length rod is the max of above 3 recursive ‘ANS’ + 1.
4. If the answer is greater than equal to infinity return 0 as it cannot be cut into rods of length ‘X’ ,’Y’ and ‘Z’. Else return the ‘ANS’. 