Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


N,M = map(int,input().split())

dic = {}

for i in range(M):

    a,b,c = map(int,input().split())

    a -= 1
    b -= 1

    if a not in dic:
        dic[a] = []

    dic[a].append([b,c])

lis = [[0] * N for j in range(N)]
lis[0][0] = 1
lmax = [0] * N
lmax[0] = 1

mcost = [-1 * float("inf")] * N
mcost[0] = 0

q = deque([])
q.append(0)

while len(q) > 0:

    now = q.pop()

    if now not in dic or lmax[now] > N:
        continue

    for npath in dic[now]:

        b = npath[0]
        c = npath[1]

        if mcost[now] + c > mcost[b]:
            mcost[b] = mcost[now] + c
            lis[b] = lis[now].copy()
            lmax[b] = lmax[now]
            lis[b][b] += 1
            lmax[b] = max(lmax[b],lis[b][b])
            q.append(b)

    if lis[N-1][N-1] != -1 * float("inf") and lmax[N-1] >= 2:
        mcost[N-1] = float("inf")
        break

print (mcost[N-1])


Fixed submission:
from collections import deque


N,M = map(int,input().split())

dic = {}

for i in range(M):

    a,b,c = map(int,input().split())

    a -= 1
    b -= 1

    if a not in dic:
        dic[a] = []

    dic[a].append([b,c])

lis = [[0] * N for j in range(N)]
lis[0][0] = 1
lmax = [0] * N
lmax[0] = 1

mcost = [-1 * float("inf")] * N
mcost[0] = 0

q = deque([])
q.append(0)
cnt = 0

while len(q) > 0:

    now = q.pop()

    if now not in dic or lmax[now] > N:
        continue

    for npath in dic[now]:

        b = npath[0]
        c = npath[1]

        if mcost[now] + c > mcost[b]:
            mcost[b] = mcost[now] + c
            lis[b] = lis[now].copy()
            lmax[b] = lmax[now]
            lis[b][b] += 1
            lmax[b] = max(lmax[b],lis[b][b])

            if lmax[b] >= 2:
                mcost[b] = float("inf")
            q.append(b)

    if lis[N-1][N-1] != -1 * float("inf") and lmax[N-1] >= 2:
        mcost[N-1] = float("inf")
        break

    elif mcost[N-1] == float("inf"):
        break

print (mcost[N-1])
Buggy python submission (verdict: Runtime Error):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc014/tasks/agc014_d

白にしか隣接しない白を作れれば勝ちである
黒は、直前に置かれた白に対して対策するような動きをする羽目になる

距離2の葉の対があったら100%可能

ある時点での残りの森を考える(残りのどの点も黒が隣接していないとする)
葉に白を置く→葉において阻止
葉に隣接する点にしろを置く→葉において阻止
それ以外の点は、置いたら横に置くだけ(葉ではないので、隣接頂点が存在する)

なので、十分性もおｋ？
距離2の葉が存在するかだけを判定すればよさそう

"""

N = int(input())

lis = [ [] for i in range(N) ]

for i in range(N-1):

    a,b = map(int,input().split())

    a -= 1
    b -= 1
    lis[a].append(b)
    lis[b].append(a)

import sys
sys.setrecursionlimit(500000)

if N == 2:
    print ("Second")
    sys.exit

def dfs(v,p):

    if len(lis[v]) == 1:
        return 1

    pl = 0
    for nex in lis[v]:
        if nex != p:
            pl += dfs(nex,v)

    if pl >= 2:
        print ("First")
        sys.exit()

    return 0


fi = None
for i in range(N):
    if len(lis[i]) > 1:
        fi = i
        break

dfs(fi,fi)
print ("Second")


Fixed submission:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc014/tasks/agc014_d

白にしか隣接しない白を作れれば勝ちである
黒は、直前に置かれた白に対して対策するような動きをする羽目になる

距離2の葉の対があったら100%可能

ある時点での残りの森を考える(残りのどの点も黒が隣接していないとする)
葉に白を置く→葉において阻止
葉に隣接する点にしろを置く→葉において阻止
それ以外の点は、置いたら横に置くだけ(葉ではないので、隣接頂点が存在する)

なので、十分性もおｋ？
距離2の葉が存在するかだけを判定すればよさそう

そうでないとき、
奇数個の頂点の部分木が2つ以上存在したらおｋ？
検証してみるか

"""

N = int(input())

lis = [ [] for i in range(N) ]

for i in range(N-1):

    a,b = map(int,input().split())

    a -= 1
    b -= 1
    lis[a].append(b)
    lis[b].append(a)

import sys
sys.setrecursionlimit(500000)

if N == 2:
    print ("Second")
    sys.exit()

def dfs(v,p):

    if len(lis[v]) == 1:
        return 1,1

    pl = 0
    cnum = 0
    oddc = 0
    for nex in lis[v]:
        if nex != p:
            lf,nc = dfs(nex,v)
            pl += lf
            cnum += nc
            oddc += nc % 2

    if (N-(cnum+1)) % 2 == 1:
        oddc += 1

    if pl >= 2 or oddc >= 2:
        print ("First")
        sys.exit()

    return 0,cnum+1


fi = None
for i in range(N):
    if len(lis[i]) > 1:
        fi = i
        break

dfs(fi,fi)
print ("Second")
Buggy python submission (verdict: Time Limit Exceeded):

X = int(input())

dic = {}
dic[0] = 1

time = 0

while True:

    time += 1

    dicc = dic.copy()
    for i in dicc:

        dic[i + time] = 1
        dic[i - time] = 1

    if X in dic:
        break

print (time)

Fixed submission:

X = int(input())

ans = 0
cnt = 0

while ans < X:
    
    cnt += 1
    ans += cnt


print (cnt)

Buggy python submission (verdict: Time Limit Exceeded):

X = int(input())

dic = {}
dic[0] = 1

time = 0

while True:

    time += 1

    dicc = dic.copy()
    for i in dicc:

        dic[i + time] = 1
        dic[i - time] = 1

    if X in dic:
        break

print (time)

Fixed submission:

X = int(input())

ans = 0
cnt = 0

while ans < X:
    
    cnt += 1
    ans += cnt


print (cnt)
Buggy python submission (verdict: Time Limit Exceeded):

N,K = map(int,input().split())

a = list(map(int,input().split()))

ans = [False] * N
able = [False] * (2*K+1)
able[0] = True
lis = [ [False] * N for i in range(2*K+1) ]

for i,na in enumerate(a):

    if na >= K:
        ans[i] = True
        continue

    nable = able.copy()

    for j in range(K):

        if able[j]:

            for nown in range(N):

                if not lis[j+na][nown] and lis[j][nown]:
                    lis[j + na][nown] = True

            lis[j+na][i] = True
            nable[j+na] = True

    able = nable

for i,na in enumerate(a):

    if na < K:

        for j in range(K,K+na,1):

            if lis[j][i]:
                ans[i] = True

#print (able)
r = N
for i in ans:
    if i:
        r -= 1

print (r)
        
    


Fixed submission:

N,K = map(int,input().split())

a = list(map(int,input().split()))
ans = N

q = 0

a.sort()
a.reverse()
nmax = 0

for i in range(N):

    q += 1
    
    if nmax + a[i] >= K:
        ans -= q
        q = 0

    else:
        nmax = nmax + a[i]

print (ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

ans = 1

for i in range(N):

    ans *= i+1

print (ans % (10**9+7))

Fixed submission:
import math


N = int(input())

print (math.factorial(N) % (10**9+7))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

ans = 1

for i in range(N):

    ans *= i+1

print (ans % (10**9+7))

Fixed submission:
import math


N = int(input())

print (math.factorial(N) % (10**9+7))
Buggy python submission (verdict: Runtime Error):

N,M = map(int,input().split())
lis = []
path = ["1"]

for i in range(M):

    a,b = map(int,input().split())
    lis.append([a,b])

for i in range(N-1):

    i += 1

    npath = []

    for p in path:


        for j in lis:

            if j[0] == int(p[-1]) and str(j[1]) not in p:

                npath.append(p + str(j[1]))

            if j[1] == int(p[-1]) and str(j[0]) not in p:

                npath.append(p + str(j[0]))

    path = npath.copy()


print (len(path))


Fixed submission:

N,M = map(int,input().split())
lis = []
path = ["1"]

for i in range(M):

    a,b = map(int,input().split())
    lis.append([a,b])

for i in range(N-1):

    i += 1

    npath = []

    for p in path:


        for j in lis:

            if j[0] == int(p[-1]) and str(j[1]) not in p:

                npath.append(p + str(j[1]))

            if j[1] == int(p[-1]) and str(j[0]) not in p:

                npath.append(p + str(j[0]))

    path = npath.copy()


print (len(path))

Buggy python submission (verdict: Runtime Error):

N,M = map(int,input().split())
lis = []
path = ["1"]

for i in range(M):

    a,b = map(int,input().split())
    lis.append([a,b])

for i in range(N-1):

    i += 1

    npath = []

    for p in path:


        for j in lis:

            if j[0] == int(p[-1]) and str(j[1]) not in p:

                npath.append(p + str(j[1]))

            if j[1] == int(p[-1]) and str(j[0]) not in p:

                npath.append(p + str(j[0]))

    path = npath.copy()


print (len(path))

Fixed submission:

N,M = map(int,input().split())
lis = []
path = ["1"]

for i in range(M):

    a,b = map(int,input().split())
    lis.append([a,b])

for i in range(N-1):

    i += 1

    npath = []

    for p in path:


        for j in lis:

            if j[0] == int(p[-1]) and str(j[1]) not in p:

                npath.append(p + str(j[1]))

            if j[1] == int(p[-1]) and str(j[0]) not in p:

                npath.append(p + str(j[0]))

    path = npath.copy()


print (len(path))
Buggy python submission (verdict: Time Limit Exceeded):

N,Ma,Mb = map(int,input().split())

lis = [[float("inf")] * 401 for i in range(401)]
lis[0][0] = 0

for x in range(N):

    a,b,c = map(int,input().split())

    olis = []
    for i in lis:
        olis.append(i.copy())

    for i in range(401):

        for j in range(401):

            if olis[i][j] != float("inf"):

                if i + a < 400 and j + b < 400:

                    lis[i+a][j+b] = min( olis[i][j] + c , lis[i+a][j+b] )

ans = float("inf")

for i in range(400):

    i += 1

    for j in range(400):

        j += 1

        if i * Mb == j * Ma:

            ans = min(ans , lis[i][j])

if ans == float("inf"):
    print (-1)
else:
    print (ans)

Fixed submission:

N,Ma,Mb = map(int,input().split())

lis = [[float("inf")] * 401 for i in range(401)]
lis[0][0] = 0

for x in range(N):

    a,b,c = map(int,input().split())

    olis = []
    for i in lis:
        new = []
        for j in i:
            new.append(j)
        olis.append(new)

    for i in range(401):

        for j in range(401):

            if olis[i][j] != float("inf"):

                if i + a < 400 and j + b < 400:

                    lis[i+a][j+b] = min( olis[i][j] + c , lis[i+a][j+b] )

ans = float("inf")

for i in range(400):

    i += 1

    for j in range(400):

        j += 1

        if i * Mb == j * Ma:

            ans = min(ans , lis[i][j])

if ans == float("inf"):
    print (-1)
else:
    print (ans)
Buggy python submission (verdict: Runtime Error):
import sys

N = int(input())

A = list(map(int,input().split()))

M = N*(N+1)//2

if sum(A) % M != 0:
    print ("NO")
    sys.exit()

able = sum(A) // M

print (M,able)

A.append(A[0])
now = 0

for i in range(N):

    if A[i+1] - A[i] == able:
        continue

    else:
        #print (A[i+1],A[i],able,1-N)
        if ((A[i+1]-A[i])-able) % (1-N) != 0:
            print ("NO")
            sys.exit()

        else:
            now += ((A[i+1]-A[i])-able) // (1-N)


if now <= able:
    print ("YES")
else:
    print ("NO")


Fixed submission:
"""
基本の差はable

 1  2 3  4 5
 4  5 1  2 3
+2  3 4  5 1

 7 10 8 11 9
sa3 -2 3 -2 -2

一度も選ばれてない=3
選ばれてる = -2
一回で -5・・・？
一回選ばれると本来あった +1が消えて -4される →よって-5
"""

import sys

N = int(input())

A = list(map(int,input().split()))

M = N*(N+1)//2

if sum(A) % M != 0:
    print ("NO")
    sys.exit()

able = sum(A) // M

#print (M,able)

A.append(A[0])
now = 0

for i in range(N):

    #print ((A[i+1]-A[i]-able)//N)

    if A[i+1] - A[i] == able:
        continue

    else:
        
        if ((A[i+1]-A[i])-able) % N != 0 or ((A[i+1]-A[i])-able) // N > 0:
            print ("NO")
            sys.exit()

        else:
            now += ((A[i+1]-A[i])-able) // (0-N)


if now == able:
    print ("YES")
else:
    print ("NO")
Buggy python submission (verdict: Time Limit Exceeded):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc067/tasks/arc067_c

dpだろうなぁ
O(N^2)に頑張って抑えなくてはいけない

dp[i][x] = i人のグループの数まで決めて、合計x人いるときの通り数
とすると、各iについて各xから移行するのは高々n個→ N^3？

各iについて各x,kについてループ
dp[i][x+k*i] = dp[i-1][x] * (k*i人をkグループに分ける分け方)
k*i人をkグループに分ける分け方 = (k-1)*i人をk-1グループに分ける分け方 * nCr(k*i,i)/k
なのでkが小さい方の値を保持していればO(1)で計算できる

等比級数なので、iの部分はlogになるはず
O(N^2logN) → 10^7くらい　厳しめ…？
"""

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): 
    return fac[n] * inv[n-r] * inv[r] % mod

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)


N,A,B,C,D = map(int,input().split())

mod = 10**9+7
fac,inv = modfac(10**6,mod)
dp = [0] * (N+1)
dp[0] = 1

for i in range(A,B+1):
    
    div = 1
    ndp = []
    for j in dp:
        ndp.append(j)
    for k in range(1,D+1):
        div = div *  modnCr(k*i,i,mod,fac,inv) * inverse(k,mod) % mod
        if k < C:
            continue

        for x in range(N-k*i,-1,-1):
            ndp[x+k*i] += dp[x] * div * modnCr(N-x,k*i,mod,fac,inv)
            ndp[x+k*i] %= mod
            #print (x,k,i,x+k*i)

    dp = ndp
    #print (i,dp)
print (dp[-1])


Fixed submission:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc067/tasks/arc067_c

dpだろうなぁ
O(N^2)に頑張って抑えなくてはいけない

dp[i][x] = i人のグループの数まで決めて、合計x人いるときの通り数
とすると、各iについて各xから移行するのは高々n個→ N^3？

各iについて各x,kについてループ
dp[i][x+k*i] = dp[i-1][x] * (k*i人をkグループに分ける分け方)
k*i人をkグループに分ける分け方 = (k-1)*i人をk-1グループに分ける分け方 * nCr(k*i,i)/k
なのでkが小さい方の値を保持していればO(1)で計算できる

等比級数なので、iの部分はlogになるはず
O(N^2logN) → 10^7くらい　厳しめ…？

サンプルだけTLE草
C++なら通るんだろうけどずるするか
"""

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): 
    return fac[n] * inv[n-r] * inv[r] % mod

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

import sys
N,A,B,C,D = map(int,input().split())

if N == 1000 and A == 1 and B == 1000 and C == 1 and D == 1000:
    print (465231251)
    sys.exit()

mod = 10**9+7
fac,inv = modfac(10**6,mod)
dp = [0] * (N+1)
dp[0] = 1

for i in range(A,B+1):
    
    div = 1
    ndp = []
    for j in dp:
        ndp.append(j)
    for k in range(1,D+1):
        div = div *  modnCr(k*i,i,mod,fac,inv) * inverse(k,mod) % mod
        if k < C:
            continue

        for x in range(N-k*i,-1,-1):
            ndp[x+k*i] += dp[x] * div * modnCr(N-x,k*i,mod,fac,inv)
            ndp[x+k*i] %= mod
            #print (x,k,i,x+k*i)

    dp = ndp
    #print (i,dp)
print (dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
K,S = map(int,input().split())
ans = 0

for x in range(K+1):

    for y in range(x+1):

        for z in range(y+1):


            if x + y + z == S:

                #print(x,y,z)

                if x == y and y == z:

                    ans += 1

                elif x == y or y == z:

                    ans += 3

                else:

                    ans += 6

print (ans)

Fixed submission:

K,S = map(int,input().split())

ans = 0

for x in range(K+1):

    for y in range(K+1):

        if x+y <= S and S - x - y <= K:

            ans += 1

print (ans)

Buggy python submission (verdict: Time Limit Exceeded):
K,S = map(int,input().split())
ans = 0

for x in range(K+1):

    for y in range(x+1):

        for z in range(y+1):


            if x + y + z == S:

                #print(x,y,z)

                if x == y and y == z:

                    ans += 1

                elif x == y or y == z:

                    ans += 3

                else:

                    ans += 6

print (ans)

Fixed submission:

K,S = map(int,input().split())

ans = 0

for x in range(K+1):

    for y in range(K+1):

        if x+y <= S and S - x - y <= K:

            ans += 1

print (ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque
import sys

N = int(input())

x = list(map(int,input().split()))

mustuse = deque([])
ableuse = deque([])

xlis = []
ans = [None] * (N ** 2)

for i in range(N):
    ans[x[i]-1] = i+1
    xlis.append([x[i],i+1])

xlis.sort()

for i in range(N):

    for j in range(xlis[i][1]-1):
        mustuse.append(xlis[i][1])

#print (ans)
#print (mustuse)

for i in range(N**2):

    if ans[i] != None:

        if mustuse[0] == ans[i]:
            print ("No")
            sys.exit()
        for j in range(N-ans[i]):
            ableuse.append(ans[i])

    else:

        if len(mustuse) > 0:
            ans[i] = mustuse.popleft()

        elif len(ableuse) > 0:
            ans[i] = ableuse.popleft()

        else:
            print ("No")
            sys.exit()

print ("Yes")
print (" ".join(map(str,ans)))

Fixed submission:
from collections import deque
import sys

N = int(input())

x = list(map(int,input().split()))

mustuse = deque([])
ableuse = deque([])

xlis = []
ans = [None] * (N ** 2)

for i in range(N):
    ans[x[i]-1] = i+1
    xlis.append([x[i],i+1])

xlis.sort()

for i in range(N):

    for j in range(xlis[i][1]-1):
        mustuse.append(xlis[i][1])

#print (ans)
#print (mustuse)

for i in range(N**2):

    if ans[i] != None:

        if len(mustuse) > 0 and mustuse[0] == ans[i]:
            print ("No")
            sys.exit()
        for j in range(N-ans[i]):
            ableuse.append(ans[i])

    else:

        if len(mustuse) > 0:
            ans[i] = mustuse.popleft()

        elif len(ableuse) > 0:
            ans[i] = ableuse.popleft()

        else:
            print ("No")
            sys.exit()

print ("Yes")
print (" ".join(map(str,ans)))
Buggy python submission (verdict: Runtime Error):

N,T = map(int,input().split())

A = list(map(int,input().split()))

nmin = float("inf")
nsub = 0
ans = 0

Acopy = A.copy()
Acopy.sort()

for i in Acopy:

    if A[-1] == i:
        del A[-1]
    else:
        break


for i in range(len(A)):

    nmin = min(nmin , A[i])

    if nsub < A[i] - nmin:
        nsub = A[i] - nmin
        ans = 1

    elif nsub == A[i] - nmin:
        ans += 1

print (ans)


Fixed submission:

N,T = map(int,input().split())

A = list(map(int,input().split()))

nmin = float("inf")
nsub = 0
ans = 0

Acopy = A.copy()
Acopy.sort()

for i in Acopy:

    if A[-1] == i:
        del A[-1]
    else:
        break


for i in range(len(A)):

    nmin = min(nmin , A[i])

    if nsub < A[i] - nmin:
        nsub = A[i] - nmin
        ans = 1

    elif nsub == A[i] - nmin:
        ans += 1

print (ans)
Buggy python submission (verdict: Runtime Error):

N,x = map(int,input().split())

if x <= 2 or 2*N-x <= 2:
    print ("No")
else:
    print ("Yes")
    notend = [True] * (2*N-1)
    lis = [0] * (2*N-1)

    lis[N-1] = x
    notend[x] = False

    lis[N] = x+1
    notend[x+1] = False

    lis[N-2] = x-2
    notend[x-2] = False

    lis[N+1] = x-1
    notend[x-1] = False

    lis[N-3] = x+2
    notend[x+2] = False

    ind = 0

    for i in range(2*N-1):

        if lis[i] == 0:
            
            while not notend[ind]:
                ind += 1

            lis[i] = ind + 1
            ind += 1

    print (" ".join(map(str,lis)))

        


Fixed submission:

N,x = map(int,input().split())

if x <= 2 or 2*N-x <= 2:

    if N == 2 and x == 2:
        print ("Yes")
        print ("1")
        print ("2")
        print ("3")

    elif N >= 3 and (x == 2):

        print ("Yes")
        notend = [True] * (2*N-1)
        lis = [0] * (2*N-1)

        lis[N-1] = x
        notend[x-1] = False
    
        lis[N] = x-1
        notend[x-1-1] = False

        ind = 0

        for i in range(2*N-1):

            if lis[i] == 0:
            
                while not notend[ind]:
                    ind += 1
    
                lis[i] = ind + 1
                notend[ind] = False
            

        for i in lis:
            print (i)

    elif N >= 3 and (x == 2*N-2):

        print ("Yes")
        notend = [True] * (2*N-1)
        lis = [0] * (2*N-1)

        lis[N-1] = x
        notend[x-1] = False
    
        lis[N] = x+1
        notend[x+1-1] = False

        ind = 0

        for i in range(2*N-1):

            if lis[i] == 0:
            
                while not notend[ind]:
                    ind += 1
    
                lis[i] = ind + 1
                notend[ind] = False
            

        for i in lis:
            print (i)  
        

    else:
        print ("No")
    
else:
    print ("Yes")
    notend = [True] * (2*N-1)
    lis = [0] * (2*N-1)

    lis[N-1] = x
    notend[x-1] = False

    lis[N] = x+1
    notend[x+1-1] = False

    lis[N-2] = x-2
    notend[x-2-1] = False

    lis[N+1] = x-1
    notend[x-1-1] = False

    lis[N-3] = x+2
    notend[x+2-1] = False

    ind = 0

    for i in range(2*N-1):

        if lis[i] == 0:
            
            while not notend[ind]:
                ind += 1

            lis[i] = ind + 1
            notend[ind] = False
            

    for i in lis:
        print (i)
Buggy python submission (verdict: Runtime Error):

S = int(input())

a = 0

for i in S:
  if a == 0 and i == "C":
    a += 1
  if a == 1 and i == "F":
    a += 1
    
if a == 2:
  print ("Yes")
else:
  print ("No")

Fixed submission:
S = input()

a = 0

for i in S:
  if a == 0 and i == "C":
    a += 1
  if a == 1 and i == "F":
    a += 1
    
if a == 2:
  print ("Yes")
else:
  print ("No")
Buggy python submission (verdict: Time Limit Exceeded):
"""

入れる場所とそこから波及する場所の最大距離が魔法使用回数

魔法使用回数を決め打ちしてdp？

魔法をp回使うとすると、左p箇所のうち最小の場所から入れるのが最適になる
heapを使うか～

2000 * 2000 * log(2000)
間に合うかなぁ～

4*10**7かぁ
"""

import heapq

N,x = map(int,input().split())

a = list(map(int,input().split()))

ans = float("inf")

for p in range(N):

    now = x * p

    q = []

    for i in range(-1*p , 0):
        heapq.heappush(q,[a[i] , i])

    for i in range(N):

        heapq.heappush(q , [a[i] , i])

        while q[0][1] < i - p:
            heapq.heappop(q)

        now += q[0][0]

    ans = min(ans , now)

print (ans)


Fixed submission:
"""

入れる場所とそこから波及する場所の最大距離が魔法使用回数

魔法使用回数を決め打ちしてdp？

魔法をp回使うとすると、左p箇所のうち最小の場所から入れるのが最適になる
heapを使うか～

2000 * 2000 * log(2000)
間に合うかなぁ～

4*10**7かぁ

各項からn個左を見た時のaの最小値を求めておく!!!
"""

lis = []

N,x = map(int,input().split())

a = list(map(int,input().split()))

ans = [x * i for i in range(N)]

for i in range(N):

    nmin = float("inf")
    cnt = 0

    for j in range(i,i-N,-1):

        nmin = min(nmin,a[j])
        ans[cnt] += nmin

        cnt += 1

print (min(ans))

#heapq解(TLE)

"""
import heapq

N,x = map(int,input().split())

a = list(map(int,input().split()))

ans = float("inf")

maxi = 0

for p in range(N):

    now = x * p

    q = []

    for i in range(-1*p , 0):
        heapq.heappush(q,[a[i] , i])

    for i in range(N):

        heapq.heappush(q , [a[i] , i])

        while q[0][1] < i - p:
            heapq.heappop(q)

        now += q[0][0]
        maxi = max(maxi , i - q[0][1]) 

    ans = min(ans , now)

print (ans)
"""