Pls use C ++

3. (6 points) Write a program to find the optimal solution of the rod cutting problem. For this Step 1. In the main function, read the input from a file "input.txt" which has the following ormat: 4 1 5 8 9 The first number specify the length of rod, and then the next value specify the price of selling rod of length 1, and then the next value specify the price of length 2, and so on. Read the first number in a variable n, then dynamically create an array p of size n +1, and then store the price of rod length i in p[i] (ignore the index 0) Step 2. Implement the following function prototype: int *RodCut (int *p, int n) which takes the price vector p and the length n as its input, and it outputs a vector, say cut, that stores how to optimally cut the rod, i.e. cut[i] stores the optimal size of the first piece to cut off from the rod of length i. It should also prints the optimal revenue as: Optimal Revenue: 10 Step 3. Call RodCut in the main function with the input read in Step 1, and output the optimal cut. For example, your answer in case of the above input instance should be Pieces to sell: 2 2 3. (6 points) Write a program to find the optimal solution of the rod cutting problem. For this Step 1. In the main function, read the input from a file "input.txt" which has the following ormat: 4 1 5 8 9 The first number specify the length of rod, and then the next value specify the price of selling rod of length 1, and then the next value specify the price of length 2, and so on. Read the first number in a variable n, then dynamically create an array p of size n +1, and then store the price of rod length i in p[i] (ignore the index 0) Step 2. Implement the following function prototype: int *RodCut (int *p, int n) which takes the price vector p and the length n as its input, and it outputs a vector, say cut, that stores how to optimally cut the rod, i.e. cut[i] stores the optimal size of the first piece to cut off from the rod of length i. It should also prints the optimal revenue as: Optimal Revenue: 10 Step 3. Call RodCut in the main function with the input read in Step 1, and output the optimal cut. For example, your answer in case of the above input instance should be Pieces to sell: 2 2