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

def run():
    # sys.stdin.readline()
    import sys
    input = sys.stdin.readline
    r,c,k = map(int,input().split())
    t = [[0 for i in range(c)] for i in range(r)]
    for i in range(k):
        a,b,z = map(int,input().split())
        t[a-1][b-1] = z
    t = tuple(t)
    dp = [[[0 for i in range(c)]for i in range(r)]for i in range(4)]
    dp[0][0][0] = 0
    dp[1][0][0] = t[0][0]
    dp[2][0][0] = t[0][0]
    dp[3][0][0] = t[0][0]
    for i in range(r-1):
        dp[0][i+1][0] = dp[1][i][0]
        for j in range(1,4):
            dp[j][i+1][0] = dp[1][i][0]+t[i+1][0]
    for i in range(c-1):
        dp[0][0][i+1] = 0
        for j in range(1,4):
            dp[j][0][i+1] = max(dp[1][0][i],t[0][i+1])
        for j in range(2,4):
            dp[j][0][i+1] = max(dp[2][0][i],dp[1][0][i]+t[0][i+1])
        dp[3][0][i+1] = max(dp[3][0][i],dp[2][0][i]+t[0][i+1])
    for i in range(r-1):
        for j in range(c-1):
            for s in range(0,4):
                dp[s][i+1][j+1] =  max(dp[0][i+1][j],dp[3][i][j+1])
            for s in range(1,4):
                dp[s][i+1][j+1] = max(dp[0][i+1][j]+t[i+1][j+1],dp[1][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
            for s in range(2,4):
                dp[s][i+1][j+1] = max(dp[1][i+1][j]+t[i+1][j+1],dp[2][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
            dp[3][i+1][j+1] = max(dp[2][i+1][j]+t[i+1][j+1],dp[3][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
    print(dp[3][r-1][c-1])

if __name__ == "__main__":
    run()

### FIXED CODE ###

def run():
    # sys.stdin.readline()
    import sys
    input = sys.stdin.readline
    r,c,k = map(int,input().split())
    t = [[0 for i in range(c)] for i in range(r)]
    for i in range(k):
        a,b,z = map(int,input().split())
        t[a-1][b-1] = z
    t = tuple(t)
    dp = [[[0 for i in range(c)]for i in range(r)]for i in range(4)]
    dp[0][0][0] = 0
    dp[1][0][0] = t[0][0]
    dp[2][0][0] = t[0][0]
    dp[3][0][0] = t[0][0]
    for i in range(r-1):
        dp[0][i+1][0] = dp[1][i][0]
        for j in range(1,4):
            dp[j][i+1][0] = dp[1][i][0]+t[i+1][0]
    for i in range(c-1):
        dp[0][0][i+1] = 0
        for j in range(1,4):
            dp[j][0][i+1] = max(dp[1][0][i],t[0][i+1])
        for j in range(2,4):
            dp[j][0][i+1] = max(dp[2][0][i],dp[1][0][i]+t[0][i+1])
        dp[3][0][i+1] = max(dp[3][0][i],dp[2][0][i]+t[0][i+1])
    for i in range(r-1):
        for j in range(c-1):
            u = max(dp[0][i+1][j],dp[3][i][j+1])
            for s in range(0,4):
                dp[s][i+1][j+1] =  u
            u = max(dp[0][i+1][j]+t[i+1][j+1],dp[1][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
            for s in range(1,4):
                dp[s][i+1][j+1] = u
            u = max(dp[1][i+1][j]+t[i+1][j+1],dp[2][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
            for s in range(2,4):
                dp[s][i+1][j+1] = u
            dp[3][i+1][j+1] = max(dp[2][i+1][j]+t[i+1][j+1],dp[3][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
    print(dp[3][r-1][c-1])

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

s = input()
K = int(input())
subs = []
for i in range(0, len(s)):
    for j in range(i+1, len(s)+1):
        if i == j:
            subs.append(s[i])
        else:
            subs.append(s[i:j])
subs = list(set(subs))
subs.sort()
print(subs[K-1])


### FIXED CODE ###

s = input()
K = int(input())
subs = []
for i in range(0, len(s)):
    for j in range(i+1, i+K+1):
        if i == j:
            subs.append(s[i])
        else:
            subs.append(s[i:j])
subs = list(set(subs))
subs.sort()
print(subs[K-1])
### BUGGY CODE ###



def main():
    import sys
    input = sys.stdin.readline
    
    H,W=map(int, input().split())
    A=[[1]*(W+2)for _ in range(H+2)]
    import queue
    q=queue.Queue()
    
    for i in range(H):
        S=input()
        for j in range(W):
            if S[j]=="#":
                q.put((i+1,j+1,0))
            else:
                A[i+1][j+1]=0  
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    while not q.empty():
        ii,jj,d=q.get()
        for k in range(4):
            nxt_i=ii+dx[k]
            nxt_j=jj+dy[k]
            if A[nxt_i][nxt_j]==0:
                q.put((nxt_i,nxt_j,d+1))
                A[nxt_i][nxt_j]=1
    print(d)

                
    
            

main()


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

black_idx = []
for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            black_idx.append([h,w])

distance = [[float("inf")]*W for _ in range(H)]
for b in black_idx:
    distance[b[0]][b[1]] = 0

d = deque(black_idx)
ans = 0

while d:
    y, x = d.popleft()
    for new_y, new_x in ([y+1, x], [y, x+1], [y-1, x], [y, x-1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1 and distance[y][x] + 1 < distance[new_y][new_x]:
            distance[new_y][new_x] = distance[y][x] + 1
            ans = max(ans, distance[y][x] + 1)
            d.append([new_y, new_x])

print(ans)
### BUGGY CODE ###

data1 = input("")
n = int(data1.split(" ")[0])
m = int(data1.split(" ")[1])
data2 = [0]*m
l = [0]*m
r = [0]*m
d = [0]*m
flag = 0

for i in range(m):
    data2[i] = input("")
    l[i] = int(data2[i].split(" ")[0])
    r[i] = int(data2[i].split(" ")[1])
    d[i] = int(data2[i].split(" ")[2])

for i in range(m):
    for j in range(m):
        if r[i] == l[j]:
            r[i] = r[j]
            d[i] += d[j]

for i in range(m):
    for j in range(m):
        if l[i] == l[j] and r[i] == r[j] and d[i] != d[j]:
            print("No")
            flag = 1
            break
        elif l[i] == r[j] and r[i] == l[j] and d[i] != -d[j]:
            print("No")
            flag = 1
            break
    if flag == 1:
        break
if flag == 0:
    print("Yes")

### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    def root(x):
        if par[x] == x:
            return par[x]
        r = root(par[x])
        d[x] += d[par[x]]
        par[x] = r
        return par[x]
    def same(x,y):
        return root(x) == root(y)
    def weight(x):
        root(x)
        return d[x]
    def unite(x,y,w):
        w += weight(x)
        w -= weight(y)
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
            d[x] = -w
        else:
            par[y] = x
            d[y] = w
            if rank[x] == rank[y]:
                rank[x] += 1

    n,m = LI()
    par = [i for i in range(n)]
    rank = [0 for i in range(n)]
    d = [0 for i in range(n)]
    for i in range(m):
        x,y,w = LI()
        x -= 1
        y -= 1
        if same(x,y):
            if weight(y)-weight(x) != w:
                print("No")
                quit()
        else:
            unite(x,y,w)
    print("Yes")
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()
### BUGGY CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
DP=[1000000000]*N
DP[0]=0
for i in range(1,N):
  j=1
  while j<=K and j<=i:
    DP[i]=min(DP[i],abs(h[i]-h[i-j])+DP[i-j])
    j+=1
print(DP[-1])




### FIXED CODE ###

def main():
  #import sys
  #input = sys.stdin.readline
  N,K=map(int,input().split())
  h=list(map(int,input().split()))
  DP=[0]*N
  DP[0]=0
  for i in range(1,N):
  #j=1
  #while j<=K and j<=i:
  #  DP[i]=min(DP[i],abs(h[i]-h[i-j])+DP[i-j])
  #for j in range(max(0, i-K),i):
    #DP[i]=min(DP[i],abs(h[i]-h[j])+DP[j])
    r=max(0, i-K)
    DP[i]=min([abs(h[i]-h[j])+DP[j] for j in range(r,i)])
  print(DP[-1])
if __name__ == '__main__':
  main()
### BUGGY CODE ###

def main():
  n,m=map(int,input().split())
  happ=[-int(i) for i in input().split()]
  inf=10**6
  happ.sort()
  happ.append(inf)
  from heapq import heapify,heappop,heappush
  
  
  q=[[happ[0]+happ[0],0,0],[inf]]
  heapify(q)
  ans=0
  for _ in range(m):
    ma=heappop(q)
    while q[0]==ma:
      ma=heappop(q)
    ans+=-ma[0]
    i,j=ma[1],ma[2]
    heappush(q,[happ[i+1]+happ[j],i+1,j])
    heappush(q,[happ[i]+happ[j+1],i,j+1])
  print(ans)
if  __name__=='__main__':
  main()
    

### FIXED CODE ###

def main():
    import numpy as np
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A=np.array(A)

    def cnt_shake(x): #握手の組であって合計パワーがx以上となる組みの数
        return n**2-np.searchsorted(A,x-A).sum()
  
    right=10**10*1
    left=-10**10-1
    while right-left>1:
        mid=(left+right)//2
        if cnt_shake(mid)<m:
            right=mid
        else:
            left=mid
    
    border=left  #border以上の握手をする
    C=n-np.searchsorted(A,border+1-A)
    B=np.cumsum(A[::-1])
    #print(border,A,B,C)

    s,cnt=0,0
    for i in range(n):
        if C[i]>0:
          cnt+=C[i]
          s+=B[C[i]-1]+A[i]*C[i]
    s+=border*(m-cnt)

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

N,X,M = map(int,input().split())
dps = [0,X%M]+[0 for i in range(N)]

for i in range(2,N+1):
  dps[i] = (dps[i-1]**2)%M
  
print(sum(dps))

### FIXED CODE ###

n, x, m = map(int, input().split())
mn = min(n, m)
P = []
sum_p = 0
X = [-1] * m
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        remain = P[X[x]]
        cyc = (sum_p - remain) * ((n - X[x]) // cyc_len)
        remain += P[X[x] + (n - X[x]) % cyc_len] - P[X[x]]
        print(cyc + remain)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)
### BUGGY CODE ###

N,M = map(int,input().split(" "))
ans = 0
GATE_ID = []
for i in range(M):
    GATE_ID1,GATE_ID2 = map(int,input().split(" "))
    GATE_ID.append([GATE_ID1,GATE_ID2])
#print(GATE_ID)

for i in range(N):
    CARD_ID = i+1
    #print("CARD_ID:",CARD_ID)
    ALL_GATE_PASS_COUNT = 0
    for j in range(M):
        GATE_ID1,GATE_ID2 = GATE_ID[j][0],GATE_ID[j][1]
        #print(GATE_ID1,GATE_ID2)
        if CARD_ID >= GATE_ID1 and CARD_ID <= GATE_ID2:
            ALL_GATE_PASS_COUNT += 1
            #print(CARD_ID,":PASS")
        else:
            break
    #print("ALL_GATE_PASS_COUNT:",ALL_GATE_PASS_COUNT)
    if ALL_GATE_PASS_COUNT == M:
        ans += 1
print(ans)

### FIXED CODE ###

N,M = map(int,input().split(" "))
L_list = []
R_list = []
for i in range(M):
    L,R = map(int,input().split(" "))
    L_list.append(L)
    R_list.append(R)
if min(R_list) - max(L_list) >= 0:
    print(min(R_list) - max(L_list) +1)
else:
    print(0)
### BUGGY CODE ###

n,k=map(int,input().split())
a=n
while True:
    
    if (n-k)>0:
        n=n-k
        a=n
    else:
        b=n-k
        break
   
if abs(a)>abs(b):
    print(str(abs(b)))
else:
    print(str(abs(a)))

### FIXED CODE ###

n,k=map(int,input().split())
a=n
b=(n//k)
c=n-k*b
d=c-k

  
if abs(c)>abs(d):
    print(str(abs(d)))
else:
    print(str(abs(c)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
M = N - K
A = [0] + LIST()

# dp[i][j] := 列をi個使って、最後に使ったのがj列目の時の最小コスト
dp = list2d(M+1, N+1, INF)
dp[0][0] = 0
for i in range(M):
    for j, h1 in enumerate(A):
        # 枝刈り
        if dp[i][j] == INF:
            continue
        for k in range(j+1, N+1):
            h2 = A[k]
            dp[i+1][k] = min(dp[i+1][k], dp[i][j] + max(h2 - h1, 0))
print(min(dp[M]))


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
M = N - K
A = [0] + LIST()

# dp[i][j] := 列をi個使って、最後に使ったのがj列目の時の最小コスト
dp = list2d(M+1, N+1, INF)
dp[0][0] = 0
for i in range(1, M+1):
    for j, h1 in enumerate(A):
        for k in range(max(j-N, 0), j):
            h2 = A[k]
            dp[i][j] = min(dp[i][j], dp[i-1][k] + max(h1 - h2, 0))
print(min(dp[M]))
### BUGGY CODE ###

from operator import mul
from functools import reduce


def cmb(n, r):
    r = min(n - r, r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

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

result = 0
mod = 998244353

for k in range(K + 1):
    c = cmb(N - 1, k) % mod
    m = M % mod
    n = pow(M - 1, N - k - 1, mod) % mod
    result = (result + c * m * n) % mod

print(result)


### FIXED CODE ###

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

result = 0
p = 998244353
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用


def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p


for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

for k in range(K + 1):
    c = cmb(N - 1, k, p)
    m = M % p
    n = pow(M - 1, N - k - 1, p)
    result = (result + c * m * n) % p

print(result)
### BUGGY CODE ###

n=int(input())
arr=[]

for i in range(n):
  arr.append(int(input()))
a=max(arr)

for i in range(n):
  if arr[i]!=a:
    print(a)
  else:
    print(max(arr[:i]+arr[i+1:]))

### FIXED CODE ###

n=int(input())
arr=[]

for i in range(n):
  arr.append(int(input()))
a=max(arr)

for i in range(n):
  if arr[i]==a:
    b=max(arr[:i]+arr[i+1:])
    break
    
for i in range(n):
  if arr[i]!=a:
    print(a)
  else:
    print(b)
### BUGGY CODE ###

H, W, M = map(int, input().split())
Hdst = [0]*H
Wdst = [0]*W
DST = [[0] * 2 for i in range(M)]
for i in range(M):
    hi, wi = map(int, input().split())
    Hdst[hi-1] += 1
    Wdst[wi-1] += 1
    DST[i] = [hi-1, wi-1]

Hbomb = [i for i, x in enumerate(Hdst) if x == max(Hdst)]
Wbomb = [i for i, x in enumerate(Wdst) if x == max(Wdst)]

ans = 0
for i in Hbomb:
    for j in Wbomb:
        tmp = Hdst[i] + Wdst[j]
        if [i, j] in DST:
            tmp -= 1
        if tmp > ans:
            ans = tmp

print(ans)

### FIXED CODE ###

H, W, M = map(int, input().split())
Hdst = [0]*H
Wdst = [0]*W
DST = [[0] * M for i in range(2)]
for i in range(M):
    hi, wi = map(int, input().split())
    Hdst[hi-1] += 1
    Wdst[wi-1] += 1
    DST[0][i] = hi-1
    DST[1][i] = wi-1

Hdstmax = max(Hdst)
Wdstmax = max(Wdst)
Hbomb = [i for i, x in enumerate(Hdst) if x == Hdstmax]
Wbomb = [i for i, x in enumerate(Wdst) if x == Wdstmax]

Hchk = [False]*H
Wchk = [False]*W
for i in Hbomb:
    Hchk[i] = True
for i in Wbomb:
    Wchk[i] = True

tmp = 0
for i in range(M):
    if Hchk[DST[0][i]] and Wchk[DST[1][i]]:
        tmp += 1

if len(Hbomb)*len(Wbomb) == tmp:
    print(Hdstmax + Wdstmax - 1)
else:
    print(Hdstmax + Wdstmax)
### BUGGY CODE ###

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

#a=A
#a=list(range(10))+list(range(5))
unq=[0]*len(a)
unqCt=[0]*len(a)
ans=0
ct2=1
ct3=0
while ct2 > 0:
	ct1=0
	ct2=0
	nokori=[0]*len(a)
	for i in range(len(a)):
		if a[0]==a[i]:
			#ctlist[ct1]= i
			ct1 +=1
			#print(ct1)
		else:
			nokori[ct2]=a[i]
			ct2 +=1
			#print(ct2)
	unq[ct3]=a[0]
	unqCt[ct3]=ct1
	ct3+=1
	a=nokori[:-ct1]

kakikae=ct3-K
if kakikae>0:
	ctmin=1
	while kakikae >0:
		for n in range(len(unqCt)):	
			if unqCt[n]==ctmin:
				ans+=ctmin
				kakikae-=1
				if kakikae==0:
					break
		ctmin+=1		
else:
	ans=0	
		
print(ans)

### FIXED CODE ###

import collections
import numpy

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

A = collections.Counter(A)
C=A.most_common()

if len(C)> K:
	dels=len(C) - K
	delsList=numpy.array(C[-dels:])
	ans=sum(delsList)[1]
else :
	ans=0

print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3


M = 10 ** 9 + 7

def solve(n, m, s, p):

    cnt = [0] * (n + 1)
    c = 0
    for i in range(n):
        cnt[i] = c
        if s[i] == '1':
            c += 1
    cnt[n] = c


    ans = 1
    for sp in p:
        dp = [[0] * (n + 2) for _ in range(n + 2)]
        l0, r0 = sp[0]
        c0 = cnt[l0]
        dp[1][1] = 1
        t0 = 0
        t1 = 0
        r = r0
        for tpl in sp:
            nl, nr = tpl
            nr = max(r, nr)
            nt1 = cnt[nr] - c0
            nt0 = nr - l0 - nt1
            for i in range(max(nl - l0 - t1, 0), t0 + 1):
                for j in range(t1 + 1, nt1 + 1):
                    dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1]) % M
            for i in range(t0 + 1, nt0 + 1):
                for j in range(max(nl - l0 - t0, 0), t1 + 1):
                    dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1]) % M
            for i in range(t0 + 1, nt0 + 1):
                for j in range(t1 + 1, nt1 + 1):
                    dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1]) % M
            t0 = nt0
            t1 = nt1
        ans *= dp[t0 + 1][t1 + 1]
        ans %= M

    return ans


def main():
    n, m = input().split()
    n = int(n)
    m = int(m)
    s = input()
    p = []
    ll = -1
    lr = 0
    for _ in range(m):
        l, r = input().split()
        l = int(l) - 1
        r = int(r)
        r = max(lr, r)
        if l == ll:
            sp.pop()
            sp.append((l, r))
        else:
            if lr <= l:
                sp = []
                p.append(sp)
            sp.append((l, r))
        ll = l
        lr = r

    print(solve(n, m, s, p))


if __name__ == '__main__':
    main()



### FIXED CODE ###

#!/usr/bin/env python3


M = 10 ** 9 + 7


def solve(n, m, s, lst):

    cnt = [0] * n
    t = 0
    for i in range(n):
        if s[i] == '1':
            t += 1
        cnt[i] = t


    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    r = 0
    j = 0
    for i in range(n):
        while j < m:
            lj, rj = lst[j]
            if lj <= i:
                r = max(r, rj)
                j += 1
            else:
                break
        if r <= i:
            c = cnt[i]
            if 0 < c:
                dp[i + 1][cnt[i]] = (dp[i][c] + dp[i][c - 1]) % M
            else:
                dp[i + 1][0] = dp[i][0]
        else:
            for k in range(max(0, cnt[r] - r + i), min(i + 1, cnt[r]) + 1):
                if 0 < k:
                    dp[i + 1][k] = (dp[i][k] + dp[i][k - 1]) % M
                else:
                    dp[i + 1][0] = dp[i][0]

    return dp[n][cnt[n - 1]]


def main():
    n, m = input().split()
    n = int(n)
    m = int(m)
    s = input()
    lst = []
    for _ in range(m):
        l, r = input().split()
        l = int(l) - 1
        r = int(r) - 1
        lst.append((l, r))

    print(solve(n, m, s, lst))


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

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

for i in range(a, b+1):
    if i < a+k or b-k < i:
        print(i)

### FIXED CODE ###

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

for i in range(a, min(b+1, a+k)):
    print(i)
for i in range(max(b-k+1, a+k), b+1):
    print(i)
### BUGGY CODE ###

import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	pp = []
	for i, val in enumerate(P):
		pp.append([i,val])
	pp.sort(key=lambda x:x[1],reverse=True)

	x = 0
	largeind = []
	for i in range(N):
		target = pp[i][0]
		L1ind, L2ind = -1, -1
		R1ind, R2ind = N, N

		larger = len(largeind)
		smaller = -1
		while larger-smaller!=1:
			medium = int((larger+smaller)/2)
			if largeind[medium]>target:
				larger = medium
			else:
				smaller = medium
		largeind.insert(larger,target)

		if larger-1>=0:
			L1ind = largeind[larger-1]
		if larger-2>=0:
			L2ind = largeind[larger-2]
		if larger+1<=len(largeind)-1:
			R1ind = largeind[larger+1]
		if larger+2<=len(largeind)-1:
			R2ind = largeind[larger+2]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*pp[i][1]

	# print(second_list)
	print(x)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	RR = [i+1 for i in range(N)]
	LL = [i-1 for i in range(N)]
	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort()

	x = 0
	for i in range(N):
		target = ips[P[i]-1]
		R1ind = RR[target]
		R2ind = RR[ min(R1ind,N-1) ]
		L1ind = LL[target]
		L2ind = LL[ max(L1ind,0) ]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

		if L1ind!=-1:
			RR[L1ind] = R1ind
		if R1ind!=N:
			LL[R1ind] = L1ind

	print(x)

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

N, W = map(int, input().split())
wv = (map(int, input().split()) for _ in range(N))
#print(tuple(map(tuple, wv)))
dp = [0] * (W + 1)
for w, v in wv:
    for j in range(W, w-1, -1):
        dp[j] = max(dp[j], dp[j - w] + v)
print(max(dp))

### FIXED CODE ###

# -*- coding: utf-8 -*-

import numpy as np

EDPC = "https://atcoder.jp/contests/DP/"
TDPC = "https://atcoder.jp/contests/tDPc/tasks"

################ DANGER ################
test = ""
#test = \
"""
3 8
3 30
4 50
5 60
ans 90
"""

"""
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
ans 5000000000(>int32)
"""

"""
6 15
6 5
5 6
6 4
6 6
3 5
7 2
ans 17
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################  
# np.maximum(np.array([1,3,2]), np.array([2, 1, 3]))
N, W = map(int, input2().split())
WV = np.array([tuple(map(int, input2().split())) for _ in range(N)])

dp = np.zeros(W + 1, dtype="int64")
for w, v in WV:
    dp[W:w-1:-1] = np.maximum(dp[W:w-1:-1], dp[W-w::-1] + v)

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

import numpy as np

n, m = map(int, input().strip().split())
dp = [float('inf')] * (2**n)
dp[0] = 0
for i in range(m):
    a, b = map(int, input().strip().split())
    c = map(int, input().strip().split())
    mask = 0
    for i in c:
        mask += 2**(i - 1)

    for j in range(2**n):
        dp[j | mask] = min(dp[j] + a, dp[j | mask])

print(dp[2**n - 1] if dp[2**n - 1] < float('inf') else -1)

### FIXED CODE ###

n,m = input().split(' ')
n = int(n)
m = int(m)
dp = [float('inf')]*2**n
dp[0] = 0
for i in range(m):
    a,b = input().split(' ')
    a = int(a)
    b = int(b)
    ngo = 0
    for j in input().split(' '):
        ngo += 2**(int(j)-1)
    for j in range(2**n):
        if dp[j|ngo] > dp[j]+a:
            dp[j|ngo] = dp[j]+a
    
if dp[2**n-1] == float('inf'):
    print(-1)
    exit(0)
print(dp[2**n-1])