Problem K
Purchasing Perishables

It’s the beginning of a new semester at Mines, and Katie is
planning out her grocery shopping for the foreseeable future.
For each of the next
To keep her schedule orderly, Katie has decided to only go
shopping on regular intervals. If there is a gap between
shopping trips, she will buy exactly enough meals to last until
her next purchase or until she has purchased all
Katie has a lot of work to do for her Data Structures class
and doesn’t have time to figure out an optimal interval between
shopping trips to minimize her shopping budget. Given the
prices for the next
Input
The first line of input contains a single integer
Output
The output should consist of a single integer, the minimum
budget required to purchase
Sample Input Explanations
For the first sample input, the optimal solution is for
Katie to go to the store every
For the second sample input, the first day has the lowest
price, so Katie buys all
For the third sample input, all days have the same price.
Any way of purchasing
Sample Input 1 | Sample Output 1 |
---|---|
4 4 10 9 3 |
15 |
Sample Input 2 | Sample Output 2 |
---|---|
5 15 89 19 54 30 |
75 |
Sample Input 3 | Sample Output 3 |
---|---|
3 1000000000 1000000000 1000000000 |
3000000000 |