AtCoder Grand Contest 004
翻译中…
Problem Statement
翻译中…
Snuke lives in another world, where slimes are real creatures and kept by some people. Slimes come in $N$ colors. Those colors are conveniently numbered $1$ through $N$. Snuke currently has no slime. His objective is to have slimes of all the colors together.
翻译中…
Snuke can perform the following two actions:
翻译中…
- Select a color
$i$($1≤i≤N$), such that he does not currently have a slime in color$i$, and catch a slime in color$i$. This action takes him$a_i$seconds. - Cast a spell, which changes the color of all the slimes that he currently has. The color of a slime in color
$i$($1≤i≤N-1$) will become color$i+1$, and the color of a slime in color$N$will become color$1$. This action takes him$x$seconds.
翻译中…
Find the minimum time that Snuke needs to have slimes in all $N$ colors.
翻译中…
Constraints
翻译中…
$2≤N≤2,000$$a_i$are integers.$1≤a_i≤10^9$$x$is an integer.$1≤x≤10^9$
翻译中…
Input
翻译中…
The input is given from Standard Input in the following format:
翻译中…
N x
a_1 a_2 ... a_N翻译中…
Output
翻译中…
Find the minimum time that Snuke needs to have slimes in all $N$ colors.
翻译中…
样例
Input #1
2 10
1 100
Output #1
12
Snuke can act as follows:
- Catch a slime in color $1$. This takes $1$ second.
- Cast the spell. The color of the slime changes: $1$ → $2$. This takes $10$ seconds.
- Catch a slime in color $1$. This takes $1$ second.
Input #2
3 10
100 1 100
Output #2
23
Snuke can act as follows:
- Catch a slime in color $2$. This takes $1$ second.
- Cast the spell. The color of the slime changes: $2$ → $3$. This takes $10$ seconds.
- Catch a slime in color $2$. This takes $1$ second.
- Cast the soell. The color of each slime changes: $3$ → $1$, $2$ → $3$. This takes $10$ seconds.
- Catch a slime in color $2$. This takes $1$ second.
Input #3
4 10
1 2 3 4
Output #3
10
Snuke can act as follows:
- Catch a slime in color $1$. This takes $1$ second.
- Catch a slime in color $2$. This takes $2$ seconds.
- Catch a slime in color $3$. This takes $3$ seconds.
- Catch a slime in color $4$. This takes $4$ seconds.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。