每一种宠物，要么是花 $a_i$ 购买的，要么是通过若干次转换获得的。显然答案就是购买的 $\sum a_i$ 加上 $x$ 乘所需转换次数的最大值。

枚举 $k$ 表示转换次数的最大值，现在我们要选出若干个 $a_i$ 直接购买，要找出一个最优策略。

然后我开始饭糖了

我是这么想的：

显然每一个没被选的都要从它前面第一个被选的地方推过来，考虑 DP。设计 $dp_i$ 表示前 $i$ 个中，第 $i$ 个必选且满足条件的最小值。 $dp_i=dp_j+a_j*(i-j-1)+a_i$

首先我目测这玩意没法斜率优化，其次他是一个环，我不会求答案，但我知道绝对不是 $dp_{n+i}-dp_i$。

正解

std的思路是，还是先枚举 $k$，然后每一个 $i$ 从前面 $k$ 个找最小值。

这么做保证了是从上一个选择的地方过来的。

证明如下

（感谢大佬 @ ）

考虑反证。假设 $x<y<i$，现在假设 $a_i$ 从 $a_x$ 转移过来，且 $a_y$ 选了。

$a_i$ 从 $a_x$ 而不是 $a_y$ 转移过来，说明 $a_x<a_y$，且 $x$ 到 $i$ 之间可以不选别的。这样 $a_y$ 可以从 $a_x$ 转移过来，不需要选 $a_y$，假设不成立。证明毕。

然后这个最小值可以使用 ST 表处理。但注意到这一步的决策包含了上一步的决策，所以我们可以直接维护一个 $mi_i$ 表示 $i$ 前 $k$ 个的最小值。

时间复杂度 $\Theta(n^2)$

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e>'9'||e<'0') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<3)+(x<<1)+(e^'0');
		e=getchar();
	}
	return x*y;
}
const int N=2005;
int n,x,a[N],ans;
int mi[N];
signed main() {
	freopen("collection.in","r",stdin);
	freopen("collection.out","w",stdout);
	R(n),R(x);
	for(int i=1; i<=n; ++i) {
		R(a[i]);
		mi[i]=a[i];
		ans+=a[i];
	}
	for(int k=1; k<=n; ++k) {
		int res=k*x;
		for(int i=1; i<=n; ++i) {
			mi[i]=min(mi[i],a[(i+n-k-1)%n+1]);
			res+=mi[i];
		}
		ans=min(ans,res);
	}
	cout<<ans<<"\n";
	return 0;
}