Minimum Price :
Difficulty Level : Hard
Submissions : 1038
Asked In :
Marks :100
: 19 | : 3
There are N stones in a line . The cost and type of the ith stone is $$$a_i$$$ units and i respectively. You are initially having zero stones and you wish to collect all the N types of stones type1,type2.......,typeN.
You can perform the following operation multiple times (probably zero) to change the type of all the stones in one step:
The stone of the type i will be changed to the type i+1. If i is N then change its type to 1 ($$$1 \le i \le N $$$)
Apply this operation single time cost x units.
Your task is to print the minimum price that you have to pay to get all N types of stones in your collection.
The first line contains two integers N, and X. ($$$1 \le N \le 2000$$$) ($$$0 \le x \le 10^9$$$)
Next line N space-separated integers representing the price of each stone ($$$1 \le a_i \le 10^9$$$)
For each output print the minimum price that you have to pay to get all N types of stones
3 5 50 1 50
13
