Problem 1 - RockBags (10 points) A shopkeeper in ArachnidMan's city has learned of your awesome algorithm design and programming skills, and has hired you to help decide how to package his shiny rocks for sale. While all the shiny rocks are identical, how they are grouped and packaged makes a huge difference. A bag with 8 rocks may be worth less than two bags of 4 rocks, since one bag with 8 rocks has the disadvantage of being very heavy. On the other hand, it might be worth more than two bags of 4 rocks, if people want 8 rocks but don't want to mess with two different bags. This is all very unpredictable, so the "Shiny Rock Consortium" standardizes prices and publishes a list of the value of different size bags. This is provided in a text file, where the first line gives a value n with the maximum number of rocks that can be put in a bag, followed by n lines that give the value of a size 1 bag, size 2 bag, etc. For example, if bags can hold up to 5 rocks, and a 1 rock bag is worth 5 dollars, a 2 rock bag is worth 10 dollars, a 3 rock bag is worth 15 dollars, a 4 rock bag is worth 16 dollars, and a 5 rock bag is worth 22 dollars, the input would look like this: 5 4 10 15 16 22 Your shopkeeper has exactly n shiny rocks, and wants to know how to divide them into bags to maximize his value. With the data above, he could put all 5 rocks in one bag (value 22 dollars), or could make two bags with two rocks and one bag with one rock (value 10+10+4=24 dollars). His best option, however, is one bag with two rocks and one bag with three rocks (value 10+15=25 dollars). Your task is to write a program that reads this data (from standard input, as always), and prints out the maximum possible total value. So with he input given above, your program would print out "25". Your program must be able to process inputs with up to 10,000 values, and run in less than 15 seconds