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 format: 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 plil (ignore the index 0) Step 2. Implement the following functionp 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