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 $N$ days she needs ingredients for one meal. To inform her planning, she has compiled a list of prices the store is charging for a meal for each of the next $N$ days she wishes to plan out.
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 $N$ meals. For instance, if she is planning out $4$ days and decides on an interval of $3$ days, then she will purchase $3$ meals on the first day, and $1$ meal on the fourth day for a total of $4$ meals.
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 $N$ days, help Katie determine the optimal interval and the minimum budget she needs to allocate to purchasing meals for the next $N$ days, given she will only purchase food on regular intervals.
Input
The first line of input contains a single integer $1 \leq N \leq 10^5$, the number of days for which Katie has prices. The next line contains $N$ space-separated integers $p_1, p_2, \ldots , p_ N$ ($1 \leq p_ i \leq 10^9$), where $p_ i$ is the price of a meal on the $i^{\text {th}}$ day.
Output
The output should consist of a single integer, the minimum budget required to purchase $N$ meals for the next $N$ days.
Sample Input Explanations
For the first sample input, the optimal solution is for Katie to go to the store every $3$ days. On the first day she purchases $3$ meals at a cost of $4$, and on the fourth day she purchases $1$ meal at a cost of $3$. This has a total cost of $3 \cdot 4 + 1 \cdot 3 = 15$.
For the second sample input, the first day has the lowest price, so Katie buys all $5$ meals on the first day. This has a total cost of $75$.
For the third sample input, all days have the same price. Any way of purchasing $3$ meals has a total cost of $3\, 000\, 000\, 000$.
| 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 |
