# Minimum Price DSA Problem Solution

In this post, we are going to solve Minimum Price DSA Problem from Oracle, Online Assessments conducted on 13th October,2022. Let’s have a look at the problem statement first and then try to solve the problem.

## Minimum Price DSA Problem Statement

There are N stones in a line . The cost and type of the ith stone is

${a}_{i}$$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$$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.

Input

The first line contains two integers N, and X. (

$1\le N\le 2000$$1 \le N \le 2000$) (

$0\le x\le {10}^{9}$$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}$$1 \le a_i \le 10^9$)

Output

For each output print the minimum price that you have to pay to get all N types of stones

Example
Input
3 5
50 1 50
Output
13

## Problem Solution in C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
ll n,x,res=2e18;
cin >> n >> x;
vector<ll> a(n),minn;
for(int i=0;i<n;i++){
cin >> a[i];
}
minn=a;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
minn[(i+j)%n]=min(minn[(i+j)%n],a[j]);
}
ll sum=x*i;
for(int j=0;j<n;j++){
sum+=minn[j];
}
res=min(res,sum);
}
cout << res;
return 0;
}