in c++

2. (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 n1, and then store the price of rod length i in pli] (ignore the index 0). Step 2. Implement the following function prototype int *RodCut (int *p, int n) which takes the pointer to the price array p and its length n as its input, and it outputs a pointer to an array, 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