Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


data = sys.stdin.readlines()
N, M = map(int, data[0].split())
edge = [[[] for _ in range(N)] for _ in range(3)]
for i in range(1, M + 1):
    u, v = map(int, data[i].split())
    u -= 1
    v -= 1
    edge[0][u].append(v)
    edge[1][u].append(v)
    edge[2][u].append(v)
S, T = map(lambda x: int(x) - 1, data[M + 1].split())


def dfs(n, step):
    global T, ans
    rst = False
    if n == T and step % 3 == 0:
        rst |= True
    else:
        d = step % 3
        for e in edge[d][n]:
            if status[(d + 1) % 3][e] > step + 1:
                status[(d + 1) % 3][e] = step + 1
                rst |= dfs(e, step + 1)
    return rst


INF = float('inf')
status = [[INF] * N for _ in range(3)]
ans = 10 ** 10
if dfs(S, 0):
    print(status[0][T] // 3)
else:
    print(-1)


### FIXED CODE ###

import sys
from collections import deque


data = sys.stdin.readlines()
N, M = map(int, data[0].split())
edge = [[] for _ in range(N)]
for i in range(1, M + 1):
    u, v = map(int, data[i].split())
    u -= 1
    v -= 1
    edge[u].append(v)
S, T = map(lambda x: int(x) - 1, data[M + 1].split())

visited = set()
q = deque()
q.append((0, S))
ans = 10 ** 10
while len(q) > 0:
    c, v = q.popleft()
    key = (c % 3, v)
    if key in visited:
        continue
    visited.add(key)
    if v == T and c % 3 == 0:
        ans = min(ans, c // 3)
    else:
        for e in edge[v]:
            newKey = (c + 1, e)
            q.append(newKey)

if ans == 10 ** 10:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))

lis=[(i+1)/2 for i in l]
ans=0

for i in range(n-k+1):
  l=lis[i:i+k]
  num=sum(l)
  ans=max(num,ans)
  
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))

for i in range(n):
  l[i]=(l[i]+1)/2

lis=[0]*(n+1)
for i in range(n):
  lis[i+1]=lis[i]+l[i]
  
ans=0
for i in range(n-k+1):
  num=lis[i+k]-lis[i]
  ans=max(num,ans)
  
print(ans)
### BUGGY CODE ###

import numpy as np

def main():
    N, K, Q = [int(x) for x in input().split()]
    X = np.array([K] * N)
    for _ in range(Q):
        X -= 1
        X[int(input())-1] += 1
    
    for x in X:
        if x > 0:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()


### FIXED CODE ###

import numpy as np

def main():
    N, K, Q = [int(x) for x in input().split()]
    X = np.array([K - Q] * N)
    for _ in range(Q):
        X[int(input())-1] += 1
    
    for x in X:
        if x > 0:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()
### BUGGY CODE ###

N=int(input())
ans=[0]*N
for i in range(1,N+1):
    for x in range(1,N+1):
        if x**2>i:
            break
        for y in range(x,N+1):
            if x**2+y**2>i:
                break
            for z in range(y,N+1):
                if x**2+y**2+z**2>i:
                    break
                if x**2+y**2+z**2+x*y+y*z+z*x==i:
                    ans[i-1]=3
if N>=6:
    ans[5]=1
for i in ans:
    print(i)

### FIXED CODE ###

from itertools import permutations
N=int(input())
ans=[0]*(10**6)
for x in range(1,N+1):
    if x**2>N:
        break
    for y in range(1,N+1):
        if x**2+y**2>N:
            break
        for z in range(1,N+1):
            if x**2+y**2+z**2>N:
                break
            else:
                kari=[x,y,z]
                #print(kari)
                if x**2+y**2+z**2+x*y+y*z+z*x<=10**5:
                    ans[x**2+y**2+z**2+x*y+y*z+z*x-1]+=1
                    
for i in range(N):
    print(ans[i])
### BUGGY CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def cummax(it, first=-float('inf')):
    """
    np.maximum.accumulate(arr) でもよさそう
    https://stackoverflow.com/questions/33569668/numpy-max-vs-amax-vs-maximum

    累積 max
    :param collections.Iterable it:
    :param float first:
    :return:
    """
    cm = first
    ret = []
    for v in it:
        cm = max(v, cm)
        ret.append(cm)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

# dp[k]: i | j | k == k となる i, j のうち A[i] + A[j] が最大となる i, j
#: :type: list of ((int, int), (int, int))
dp = [None] * (2 ** N)
for k in range(1, 2 ** N):
    dp[k] = [(A[0], 0), (A[k], k)]

digits = []
k = 1
while k < 2 ** N:
    digits.append(k)
    k <<= 1

for k in range(1, 2 ** N):
    for d in digits:
        if k & d == 0:
            dp[k | d] = list(sorted(set(dp[k | d] + dp[k])))[-2:]

ans = [0] * (2 ** N)
for k in range(1, 2 ** N):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2

ans = cummax(ans[1:])
print(*ans, sep='\n')


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def cummax(it, first=-float('inf')):
    """
    np.maximum.accumulate(arr) でもよさそう
    https://stackoverflow.com/questions/33569668/numpy-max-vs-amax-vs-maximum

    累積 max
    :param collections.Iterable it:
    :param float first:
    :return:
    """
    cm = first
    ret = []
    for v in it:
        cm = max(v, cm)
        ret.append(cm)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
SIZE = 2 ** N

# dp[k]: i | j | k == k となる i, j のうち A[i] + A[j] が最大となる i, j
#: :type: list of ((int, int), (int, int))
dp = [None] * SIZE
for k in range(1, SIZE):
    dp[k] = list(sorted([(A[0], 0), (A[k], k)]))

for k in range(1, SIZE):
    mask = k
    while mask < SIZE - 1:
        # kに立ってないビットを1つだけ立てる
        next_k = (mask + 1) | k
        mask |= next_k

        a1, a2 = dp[k]
        b1, b2 = dp[next_k]
        if a1 > b2:
            # dp[next_k] = a1, a2
            dp[next_k] = dp[k]
        elif b1 > a2:
            # dp[next_k] = b1, b2
            pass
        elif a2 > b2:
            dp[next_k] = b2, a2
        elif b2 > a2:
            dp[next_k] = a2, b2

ans = [0] * SIZE
for k in range(1, SIZE):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2

ans = cummax(ans[1:])
print(*ans, sep='\n')
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*(n)
for i in range(1, min(n, k+1)) :
    dp[i] = abs(h[0]-h[i])
for i in range(k+1, len(dp)) :
    minv = 10**9+7
    for j in range(1, k+1) :
        minv = min(minv, dp[i-j] + abs(h[i-j]-h[i]))
    dp[i] = minv

print(dp[n-1])


### FIXED CODE ###

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

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

dp = [0 for i in range(N)]
if N >= K :    
    for i in range(1,K+1) :
        dp[i] = abs(L[i]-L[0])
    for i in range(K+1,len(dp)) :
        state = float("inf")
        for j in range(i-K,i) :
            calc = abs(L[i]-L[j]) + dp[j]
            if state > calc :
                state = calc
        dp[i] = state
    print(dp[N-1])
else :
    print(abs(min(L[1:])-L[0]))
### BUGGY CODE ###

N, M = map(int, input().split())
demand_list = []
for _ in range(M):
    ai, bi = map(int, input().split())
    demand_list.append([ai, bi])

# ソート
demands = sorted(demand_list, key=lambda d: d[1])

# 分断開始 切断されている橋は1で表現される
cut_bilagge_list = [0 for _ in range(N)]

for demand in demands:
    # すでに分断されているのかをチェックする
    if len([1 for i in cut_bilagge_list[demand[0] - 1:demand[1] - 1] if i == 1]) > 0:
        continue

    # 分断されていないので bi - 2の橋を切断する
    cut_bilagge_list[demand[1] - 2] = 1


print(sum(1 for bilagge in cut_bilagge_list if bilagge == 1))


### FIXED CODE ###

# https://atcoder.jp/contests/abc103/tasks/abc103_d

# ToDo not yet

# biについて昇順にソートする
# それぞれのbiについて、
# 1: すでに分断されているなら何もしない
# 2: 分断されていないならbi - 1番目の橋を切断する

N, M = map(int, input().split())
demand_list = []
for _ in range(M):
    ai, bi = map(int, input().split())
    demand_list.append([ai, bi])

# ソート
demands = sorted(demand_list, key=lambda d: d[1])

# 分断開始 切断されている橋は1で表現される
# cut_bilagge_list = [0 for _ in range(N)]
cnt = 0
cut_max_len = -1

for demand in demands:
    a, b = demand
    # すでに分断されているのかをチェックする
    if a < cut_max_len:
        continue
    # if len([1 for i in cut_bilagge_list[demand[0] - 1:demand[1] - 1] if i == 1]) > 0:
    #     continue

    # 分断されていないので bi - 2の橋を切断する
    # cut_bilagge_list[demand[1] - 2] = 1
    cut_max_len = b
    cnt += 1

# print(sum(1 for bilagge in cut_bilagge_list if bilagge == 1))
print(cnt)
### BUGGY CODE ###

# B
import numpy as np

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

cost = [0]*N

cost[0] = 0
for i in range(1,N):
    cost_tmp = []
    for j in range(0,min(K,i)):
        cost_tmp.append(abs(h[i - (1+j)] - h[i]) + cost[i - (1+j)])
    cost[i] = np.min(cost_tmp)

print(cost[-1])


### FIXED CODE ###

# B(TLE) 2104ms

import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))
cost = np.zeros(N, dtype="int32")

cost[0] = 0
for i in range(1,N):
    start = 0 if i < K else i-K
    cost[i] = np.min(cost[start:i] + np.abs(h[i]-h[start:i]))

print(cost[-1])
### BUGGY CODE ###

l,r=map(int,input().split())
ans=2019
for i in range(l,r):
  for j in range(i+1,r+1):
    temp=i*j%2019
    ans=min(ans,temp)
print(ans)

### FIXED CODE ###

l,r=map(int,input().split())
i=1
temp=0
while r>2019*i:
  if l<=2019*i:
    temp=1
    break
  i=i+1

count=2019
r=r%2019
l=l%2019
for i in range(l,r+1):
  for j in range(i+1,r+1):
    temp1=(i*j)%2019
    count=min(count,temp1)

if temp==1:
  print(0)
else:
  print(count)
### BUGGY CODE ###

S = input()
len_s = len(S)
import re
def f(S):
    if ((not "01" in S) and (not "10" in S)):
        return S
    S = re.sub('01|10',"",S)
    return f(S)
print(len_s - len(f(S)))

### FIXED CODE ###

S = input()
if len(S) == 1:
    print(0)
else:
    print(min(S.count('0'), S.count('1')) * 2)
### BUGGY CODE ###

n,m=map(int,input().split())
List=sorted(list(map(int,input().split())))
for _ in range(m):
    b,c=map(int,input().split())
    List=sorted(List)
    for i in range(b):
        if List[i]<c:
            List[i]=c
        else:
            break

print(sum(List))

### FIXED CODE ###

n,m=map(int,input().split())
List=sorted(list(map(int,input().split())))
s=[]
for _ in range(m):
    s.append(list(map(int,input().split())))
s.sort(key=lambda x: x[1], reverse=True)

ans=0
j=0
for i in range(m):
    if j>=n or s[i][1]<=List[j]:
        break
    while j<n and s[i][0]>0 and s[i][1]> List[j]:
        ans+=s[i][1]
        s[i][0]-=1
        j+=1
if j>=n:
    print(ans)
else:
    print(ans+sum(List[j:]))
### BUGGY CODE ###

N,D,A=map(int,input().split())
m=sorted([int(j) for j in input().split()] for i in range(N))

def main():
  c,l=0,0
  while l<N:
    p=(m[l][1]+A-1)//A
    m[l][1],n,r,c=0,0,l+1,c+p
    while r<N and m[l][0]+2*D>=m[r][0]:
      if m[r][1]>A*p:
        m[r][1]-=A*p
        if n==0:
          n=r
      else:
        m[r][1]=0
      r+=1
    else:
      l=n if n!=0 else r

  print(c)

main()


### FIXED CODE ###

import bisect

def main():
  N,D,A=map(int,input().split())
  m=sorted([int(j) for j in input().split()] for i in range(N))

  x=[m[i][0] for i in range(N)]
  es=[0]*(N+1)
  a,c=0,0
  for i in range(N):
    c-=es[i]
    if m[i][1]>A*c:
      t=(m[i][1]-A*c+A-1)//A
      a+=t
      c+=t
      es[bisect.bisect_right(x,x[i]+2*D)]+=t
  print(a)

main()
### BUGGY CODE ###

import bisect
N = int(input())
 
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))
Cs = sorted(list(map(int, input().split())))
 
ans = 0
for c in Cs:
    i = bisect.bisect_left(Bs, c)
    for b in Bs[:i]:
        ans += bisect.bisect_left(As, b)
print(ans)

### FIXED CODE ###

import bisect
N = int(input())

As = sorted(list(map(int, input().split())))
Bs = list(map(int, input().split()))
Cs = sorted(list(map(int, input().split())))

ans = 0
for b in Bs:
    a = bisect.bisect_left(As, b)
    c = bisect.bisect_right(Cs, b)
    ans += a * (N-c)
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
store = [list(map(int,input().split())) for _ in range(N)]

for i in range(N):
    tmp = store[i]
    v = store[i][0]
    j = i - 1
    while j >= 0 and store[j][0] > v:
        store[j+1] = store[j]
        j -= 1
    store[j+1] = tmp

sumQ = 0
sumP = 0
for k in range(N):
    p = store[k][0]
    q = store[k][1]
    sumQ = sumQ + q
    sumP = sumP + p * q
    if M < sumQ:
        print(sumP-(sumQ-M)*p)
        break
    elif M == sumQ:
        print(sumP)
        break


### FIXED CODE ###

N,M = map(int,input().split())
store = [list(map(int,input().split())) for _ in range(N)]

A = sorted(store)

sumQ = 0
sumP = 0
for k in range(N):
    p = A[k][0]
    q = A[k][1]
    sumQ = sumQ + q
    sumP = sumP + p * q
    if M < sumQ:
        print(sumP-(sumQ-M)*p)
        break
    elif M == sumQ:
        print(sumP)
        break
### BUGGY CODE ###

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

num = 1
for i in range(n):
    pre_num = num
    num *= a[i]
    if i >= k:
        num /= a[i-k]
    if i >= k and num > pre_num:
        print('Yes')
    elif i >= k and num <= pre_num:
        print('No')


### FIXED CODE ###

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

for i in range(n):
    if i >= k:
        if a[i] > a[i-k]:
            print('Yes')
        else:
            print('No')
### BUGGY CODE ###

K = int(input())
A = 7
Flag = False
for T in range(1,K+1):
    if A%K==0:
        Flag = True
        break
    else:
        A = 10*A+7
print(['-1',T][Flag])

### FIXED CODE ###

K = int(input())
A = 7%K
Flag = False
for T in range(1,K+1):
    if A==0:
        Flag = True
        break
    else:
        A = (10*A+7)%K
print(['-1',T][Flag])
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
check = []
cnt = 0
i = 0
while True:
    if i not in check:
        check.append(i)
        i = a[i]-1
    elif cnt >= n:
        print(-1)
        break
    if i == 1:
        print(len(check))
        break
    cnt += 1
    

### FIXED CODE ###

n = int(input())
a = [None]
for j in range(n):
    a.append(int(input()))

i = 1
c = 0
r = [1]
while True:
    c += 1
    i = a[i]
    if i == 2:
        print(c)
        break
    if c > (10**5):
        print(-1)
        break
### BUGGY CODE ###

import sys,time
input = sys.stdin.readline

def main():
    pti = time.time()
    n = int(input())
    a = tuple(map(int,input().split()))
    b = tuple(map(int,input().split()))

    dg = 10**7

    pp = 20

    dp = [10**5]*dg

    new = set([])
    for i in range(n):
        s = (1<<i)
        dp[s*pp+i] = i
        new.add(s*dg+i)
    

    for k in range(n-1):
        tank = set([])
        if len(new) == 0:
            break
        for popelt in new:
            s,idx = popelt//dg,popelt%dg
            if (k-idx)%2 == 0:
                fr = a[idx]
            else:
                fr = b[idx]
            cnt = 0
            for j in range(n):
                if (s>>j)&1 == 0:
                    if (j-k)%2 == 1:
                        val = a[j]
                    else:
                        val = b[j]
                    if val >= fr and dp[(s+(1<<j))*pp+j] > dp[s*pp+idx]+j-cnt:
                        dp[(s+(1<<j))*pp+j] = dp[s*pp+idx]+j-cnt
                        tank.add((s+(1<<j))*dg + j)
                else:
                    cnt += 1
        new = tank
    
    res = 10**5
    s = (2**n-1)*pp
    for i in range(n):
        if res > dp[s+i]:
            res = dp[s+i]
    if res == 10**5:
        print(-1)
    else:
        print(res)


if __name__ == '__main__':
    main()

### FIXED CODE ###



def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = tuple(map(int,input().split()))
    b = tuple(map(int,input().split()))

    dg = 20

    pp = 20

    dp = [10**5]*(10**7)

    new = set([])
    for i in range(n):
        s = (1<<i)
        dp[s*pp+i] = i
        new.add(s*dg+i)

    for k in range(n-1):
        tank = set([])
        if len(new) == 0:
            break
        for popelt in new:
            s,idx = popelt//dg,popelt%dg
            if (k-idx)%2 == 0:
                fr = a[idx]
            else:
                fr = b[idx]
            cnt = 0
            for j in range(n):
                if (s>>j)&1 == 0:
                    if (j-k)%2 == 1:
                        val = a[j]
                    else:
                        val = b[j]
                    if val >= fr and dp[(s+(1<<j))*pp+j] > dp[s*pp+idx]+j-cnt:
                        dp[(s+(1<<j))*pp+j] = dp[s*pp+idx]+j-cnt
                        tank.add((s+(1<<j))*dg + j)
                else:
                    cnt += 1
        new = tank
    
    res = 10**5
    s = (2**n-1)*pp
    for i in range(n):
        if res > dp[s+i]:
            res = dp[s+i]
    if res == 10**5:
        print(-1)
    else:
        print(res)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

count = 0;

def uniq(li):
    ret = []
    for i in li:
        if i not in ret:
            ret.append(i)
    return ret

def overwrite(li, target_val, dest_val):
    cnt = 0
    for taple in enumerate(li):
        if taple[1] == target_val:
            li[taple[0]] = dest_val
            cnt += 1
    return [li, cnt]

def detect(li):
    min_num = [float("inf")]
    max_num = [0]
    for i in li:
        if max_num[0] < li.count(i):
            max_num[0] = li.count(i)
            if len(max_num) > 1:
                max_num[1] = i
            else:
                max_num.append(i)

        if min_num[0] >= li.count(i):
            min_num[0] = li.count(i)
            if len(min_num) > 1:
                min_num[1] = i
            else:
                min_num.append(i)

    return [min_num, max_num]


while k < len(uniq(a)):
    min_num, max_num = detect(a)
    a, cnt = overwrite(a, min_num[1], max_num[1])
    count += cnt

print(count)


### FIXED CODE ###

from collections import Counter
n, k = map(int, input().split())
a = list(map(int, input().split()))

def cnt_uniq(li):
    return Counter(li).values()

uniq = sorted(cnt_uniq(a), reverse = True)[k:]
print(sum(uniq))
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))

inf = 1e18
dp = [inf] * (n + 10)
dp[0] = 0
for i in range(1, n):
    for j in range(1, k + 1):
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))
print(dp[n - 1])


### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))

inf = 1e18
dp = [inf] * (n + 10)
dp[0] = 0
for i in range(1, n):
    for j in range(1, k + 1):
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))
print(dp[n - 1])
### BUGGY CODE ###

#C
n, k, q = map(int, input().split())
a = sorted([int(input()) for _ in range(q)])
j = 0
for i in range(n):
    count = a.count(i+1)
    if q - count >= k:
        print('No')
    else:
        print('Yes')
    a[:count] = []


### FIXED CODE ###

n, k, q = map(int, input().split())
a = sorted([int(input()) for _ in range(q)])
point = [k-q for _ in range(n)]
for i in range(q):
    point[a[i]-1] += 1
for j in  point:
    if j > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from sys import stdin, stdout  
  
# suppose a function called main() and 
# all the operations are performed 
def main(): 
  
    # input via readline method 
    n = stdin.readline() 
  
    # array input similar method 
    arr = [int(x) for x in stdin.readline().split()] 
  
    #initialize variable 
    summation = 1
      
    # calculate sum 
    for x in arr: 
        summation *= x 
  
    # could use inbuilt summation = sum(arr) 
    if summation>1e18:
        print("-1");
    else:
        print(summation);


    # print answer via write 
    # write method writes only 
    # string operations 
    # so we need to convert any 
    # data into string for input 
    
  
# call the main method 
if __name__ == "__main__": 
    main()     

### FIXED CODE ###

from sys import stdin, stdout  
  
# suppose a function called main() and 
# all the operations are performed 
def main(): 
  
    # input via readline method 
    n = stdin.readline() 
  
    # array input similar method 
    arr = [int(x) for x in stdin.readline().split()] 
  
    #initialize variable 
    summation = 1
    for x in arr:
        if x==0:
            summation=0
            break
    # calculate sum 
    for x in arr: 
        summation *= x
        if summation>1e18:
            summation=-1
            break
  
    # could use inbuilt summation = sum(arr) 
    if summation>1e18:
        print("-1");
    else:
        print(summation);


    # print answer via write 
    # write method writes only 
    # string operations 
    # so we need to convert any 
    # data into string for input 
    
  
# call the main method 
if __name__ == "__main__": 
    main()
### BUGGY CODE ###

N = int(input())
S = []
count = 0
for i in range(N):
    item = input()
    if item not in S:
        S.append(item)
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = set()
count = 0
for i in range(N):
    S.add(input())
print(len(S))
### BUGGY CODE ###

n,x=map(int,input().split())
a=list(map(int,input().split()))
b=[[None for _ in [0]*n] for _ in [0]*n]

for i in range(n):
	m=a[i]
	for j in range(n):
		k=i-j
		if k<0:
			k+=n
		m=min(m,a[k])
		b[j][i]=m

m=10**15
for i,j in enumerate(b):
	m=min(m,sum(j)+x*i)
print(m)

### FIXED CODE ###

n,x=map(int,input().split())
a=list(map(int,input().split()))
b=[[None for _ in [0]*n] for _ in [0]*n]

for i in range(n):
	m=a[i]
	for j in range(n):
		k=i-j
		if k<0:
			k+=n
		m=min(m,a[k])
		b[j][i]=m

m=10**15
for i,j in enumerate(b):
	m=min(m,sum(j)+x*i)
print(m)
### BUGGY CODE ###

N, A, B, C, D = map(int, input().split())
mod = 10 ** 9 + 7

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N + 2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


# n人いたときに、k人組を、x個つくる場合の数
def f(n, k, x):
    return nCr(n, k * x) * factorial[k * x] * pow(pow(factorial[k], x, mod), mod-2, mod) * inverse[x] % mod


dp = [[0] * (N + 1) for i in range(2)]
dp[0][0] = 1

for k in range(1, N + 1):  # k人からなるグループをこれから作りますよ
    if k % 2 == 1:
        dp[1] = [0] * (N + 1)
    else:
        dp[0] = [0] * (N + 1)

    for n in range(N + 1):  # すでにn人は使っちゃってますよ
        if A <= k <= B:  # グループの大きさの条件
            X = [0] + list(range(C, D + 1))
        else:
            X = [0]
        for x in X:
            if n - k * x < 0:  # はみ出る段階で打ち切りますよ
                break
            if k % 2 == 1:
                dp[1][n] += f(n, k, x) * dp[0][n - k * x] % mod
            else:
                dp[0][n] += f(n, k, x) * dp[1][n - k * x] % mod

print(dp[1][N])


### FIXED CODE ###

N, A, B, C, D = map(int, raw_input().split())
mod = 10 ** 9 + 7

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in xrange(1, N + 2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


# n人いたときに、k人組を、x個つくる場合の数
def f(n, k, x):
    return nCr(n, k * x) * factorial[k * x] * pow(pow(factorial[k], x, mod), mod-2, mod) * inverse[x] % mod


dp = [0] * (N + 1)
dp[0] = 1

for k in xrange(A, B + 1):  # k人からなるグループをこれから作りますよ
    for n in range(1, N + 1)[::-1]:  # すでにn人は使っちゃってますよ
        X = xrange(C, D + 1)
        for x in X:
            if n - k * x < 0:  # はみ出る段階で打ち切りますよ
                break
            dp[n] += f(n, k, x) * dp[n - k * x] % mod

print(dp[N] % mod)