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

class item(object):
    def __init__(self,name,Value,weight):
        self.name=name
        self.value=Value
        self.weight=weight
    def getweight(self):
        return self.weight
    def getname(self):
        return self.name
    def getvalue(self):
        return self.value
    def __str__(self):
        res="<"+str(self.name)+","+str(self.value)+","+str(self.weight)+">"
        return res
def sumV(itemlist):
    result=0
    for i in range(len(itemlist)):
        result+=itemlist[i].getvalue
    return result
def sumW(itemlist):
    result=0
    for i in range(len(itemlist)):
        result+=itemlist[i].getweight
    return result
def maxVal(toConsider,avail,result):
    if toConsider==[] or avail==0:
        result+=0
    elif toConsider[0].getweight()>avail:
        result+=maxVal(toConsider[1:],avail,result)
    else:
        withval=toConsider[0].getvalue()+maxVal(toConsider[1:],avail-toConsider[0].getweight(),result)
        #とるかとらないかを選ぶ
        withoutval=maxVal(toConsider[1:],avail,result)
        if withval>withoutval:
            result+=withval
        else:
            result+=withoutval
    return result
N,W=map(int,input().split())
result=0
items=[]
for i in range(N):
    w,v=map(int,input().split())
    items.append(item(str(i),v,w))
"""for i in range(len(items)):
    print(items[i])"""
print(maxVal(items,W,result))




### FIXED CODE ###

def knap(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    #各nについて初期化　以下で各ｗについて0この時０とする
    for i in range(W+1):#w+1とは0~w
        dp[0][i]=0
    for i in range(N):#each n 0~N-1
        for w in range(W+1):#w 0~w
            if weight[i]<=w:#=を入れないとぎりぎりの時が困る
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])
            else:
                dp[i+1][w]=dp[i][w]
   # print(dp)
    return dp[N][W]


n,W=map(int,input().split())
w=[]
v=[]
for i in range(n):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
print(knap(n,W,w,v))
### BUGGY CODE ###

from itertools import accumulate


def solve(n, rev):
    def existence_right(rev_c):
        n2 = n * 2
        acc = [[0] * n2]
        row = [0] * n2
        for x in rev_c:
            row[n2 - x - 1] += 1
            acc.append(list(reversed(list(accumulate(row)))))
        return acc

    # How many white/black ball lower than 'k' righter than index x? (0<=x<=2N-1)
    # cost[color][k][x]
    cost = list(map(existence_right, rev))

    dp = [0] + list(accumulate(c[y] for y, c in zip(rev[1], cost[1])))
    for x, cw0, cw1 in zip(rev[0], cost[0], cost[0][1:]):
        ndp = [0] * (n + 1)
        cw0x = cw0[x]
        ndp[0] = prev = dp[0] + cw0x
        for b, (y, cb0, cb1) in enumerate(zip(rev[1], cost[1], cost[1][1:])):
            ndp[b + 1] = prev = min(dp[b + 1] + cw0x + cb1[x], prev + cw1[y] + cb0[y])
        dp = ndp
    return dp[n]


n = int(input())
# White/Black 'k' ball is what-th in whole row?
rev = [[0] * n, [0] * n]
for i in range(n * 2):
    c, a = input().split()
    a = int(a) - 1
    rev[int(c == 'B')][a] = i
print(solve(n, rev))


### FIXED CODE ###

from itertools import accumulate


def solve(n, rev):
    def existence_right(rev_c):
        n2 = n * 2
        acc = [[0] * n2]
        row = [0] * n2
        for x in rev_c:
            row[n2 - x - 1] += 1
            acc.append(list(reversed(list(accumulate(row)))))
        return acc

    # How many white/black ball lower than 'k' righter than index x? (0<=x<=2N-1)
    # cost[color][k][x]
    cost = list(map(existence_right, rev))

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for w, x in enumerate(rev[0]):
        dp[w + 1][0] = dp[w][0] + cost[0][w][x]
    for b, y in enumerate(rev[1]):
        dp[0][b + 1] = dp[0][b] + cost[1][b][y]
    for w, x in enumerate(rev[0]):
        dpw0, dpw1 = dp[w], dp[w + 1]
        cost_wx, cost_w1 = cost[0][w][x], cost[0][w + 1]
        for b, y in enumerate(rev[1]):
            dpw1[b + 1] = min(dpw0[b + 1] + cost_wx + cost[1][b + 1][x],
                              dpw1[b] + cost_w1[y] + cost[1][b][y])
    return dp[n][n]


n = int(input())
# White/Black 'k' ball is what-th in whole row?
rev = [[0] * n, [0] * n]
for i in range(n * 2):
    c, a = input().split()
    a = int(a) - 1
    rev[int(c == 'B')][a] = i
print(solve(n, rev))
### BUGGY CODE ###

N,K = map(int,input().split())
TD = [[int(x) for x in input().split()] for _ in range(N)]
TD.sort(key = lambda x: x[1], reverse=True)

T = 0
neta = []
doublecounts = []
ans = []

for i in range(K):
    T += TD[i][1]    
    if not(TD[i][0] in neta):    
        neta.append(TD[i][0])    
    else:      
        doublecounts.append(TD[i][1])    
            
ans.append(T+len(neta)**2)

for i in range(K,N):
    if(len(doublecounts)==0):
        break
    if not(TD[i][0] in neta):
        T -= doublecounts.pop(-1)
        T += TD[i][1]
        neta.append(TD[i][0])
        ans.append(T+len(neta)**2)
print(max(ans))


### FIXED CODE ###

N,K = map(int,input().split())
TD = [[int(x) for x in input().split()] for _ in range(N)]
TD.sort(key = lambda x: x[1], reverse=True)

T = 0
neta = set()
doublecounts = []
ans = []

for i in range(K):
    T += TD[i][1]    
    if not(TD[i][0] in neta):    
        neta.add(TD[i][0])       
    else:      
        doublecounts.append(TD[i][1])    
            
ans.append(T+len(neta)**2)

for i in range(K,N):
    if(len(doublecounts)==0):
        break
    if not(TD[i][0] in neta):
        T -= doublecounts.pop(-1)
        T += TD[i][1]
        neta.add(TD[i][0])   
        ans.append(T+len(neta)**2)
print(max(ans))
### BUGGY CODE ###

import numpy as np

D=int(input())
c=np.array(list(map(int,input().split())))
s=[list(map(int,input().split())) for _ in range(D)]
t=[np.random.randint(1,27) for _ in range(D)]

MAX=0
for _ in range(2000):
    d=np.random.randint(1,D+1)
    q=np.random.randint(1,27)
    last=np.array([0]*26)
    v=0
    for i in range(1,D+1):
        if i==d:
            v+=s[d-1][q-1]
            last[q-1]=d
            v-=np.dot(c,d-last)
            continue
        v+=s[i-1][t[i-1]-1]
        last[t[i-1]-1]=i
        v-=np.dot(c,i-last)
    if v>MAX:
        MAX=v
        t[d-1]=q

for i in range(D):
    print(t[i])

### FIXED CODE ###

import numpy as np

D=int(input())
c=np.array(list(map(int,input().split())))
s=[list(map(int,input().split())) for _ in range(D)]
t=[np.random.randint(1,27) for _ in range(D)]

MAX=0
for _ in range(1000):
    d=np.random.randint(1,D+1)
    q=np.random.randint(1,27)
    last=np.array([0]*26)
    v=0
    for i in range(1,D+1):
        if i==d:
            v+=s[d-1][q-1]
            last[q-1]=d
            v-=np.dot(c,d-last)
            continue
        v+=s[i-1][t[i-1]-1]
        last[t[i-1]-1]=i
        v-=np.dot(c,i-last)
    if v>MAX:
        MAX=v
        t[d-1]=q

for i in range(D):
    print(t[i])
### BUGGY CODE ###

S = input()
Q = int(input())
Query = [input() for _ in range(Q)]

for i in range(Q):
    if Query[i][0] == "1":
        # 反転
        S = S[::-1]
    else:
        if Query[i][2] == '1':
            S = Query[i][4] + S
        else:
            S = S + Query[i][4]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
Query = [input() for _ in range(Q)]
flag = True
s = "!"
for i in range(Q):
    if Query[i][0] == "1":
        if flag:
            flag = False
        else:
            flag = True
    else:
        if Query[i][2] == '1':
            if flag:
                s = Query[i][4] + s
            else:
                s = s + Query[i][4]
        else:
            if flag:
                s = s + Query[i][4]
            else:
                s = Query[i][4] + s
ans = s.replace("!", S)
if flag:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=0
for i in range(n):
  if sum(a[:i+1])>k:
    break
  elif sum(a[:i+1])+sum(b)<=k:
      ans=max(ans,i+m+1)
  for j in range(m):
    if sum(a[:i+1])+sum(b[:j+1])<=k:
      continue
    else:
      ans=max(ans,i+j+1)
      break
print(ans)

### FIXED CODE ###

import itertools
import bisect
n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=[0]+list(map(int,input().split()))
a=list(itertools.accumulate(a))
b=list(itertools.accumulate(b))
ans=0
for i in range(m+1):
  x=k-b[i]
  y=bisect.bisect_right(a,x)
  z=i+y
  if x<0:
      z=0
  ans=max(ans,z)
print(ans)
### BUGGY CODE ###

import math

k = int(input())
ans = 0

for  h in range(1, k+1):
    for i in range(1, k+1):
        for j in range(1, k+1):
            ans += math.gcd(math.gcd(h, i), j)

print(ans)

### FIXED CODE ###

from functools import reduce
import math

k = int(input())

s = 0

def gcd(*numbers):
    return reduce(math.gcd, numbers)

for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            s += gcd(i,j,l)

print(s)
### BUGGY CODE ###

import sys
#大きすぎるとダメ
sys.setrecursionlimit(3000)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)




### FIXED CODE ###

#一個だけRE、わからねえ
#解答見る
import sys
sys.setrecursionlimit(1005)
h,w=map(int,input().split())

def go_next(I,J,n):
    n+=1
    global dp,w,h
    if n>1000:
        return
    if 0<=I<h-1:
        if x[I+1][J]=="." and dp[I+1][J]>dp[I][J]+1:
            dp[I+1][J]=dp[I][J]+1
            go_next(I+1,J,n)
    if 0<I<=h-1:
        if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
            dp[I-1][J]=dp[I][J]+1
            go_next(I-1,J,n)
    if 0<=J<w-1:
        if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
            dp[I][J+1]=dp[I][J]+1
            go_next(I,J+1,n)
    if 0<J<=w-1:
        if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
            dp[I][J-1]=dp[I][J]+1
            go_next(I,J-1,n)

x=[]
for i in range(h):
    x.append(list(input()))
#print(x)
c=0
for i in range(h):
    for j in range(w):
        if x[i][j]==".":
            c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0,0)
if dp[h-1][w-1]==10000000000:
    print(-1)
else:
    print(c-dp[h-1][w-1])
### BUGGY CODE ###

N = int(input())
s = []
for _ in range(N):
    s_ = list(input())
    s.append("".join(sorted(s_)))

s2 = set(s)
cnt = [0] * len(s2)
for i in s2:
    cnt.append(s.count(i))

ans = 0
for k in range(len(cnt)):
    l = list(range(0,cnt[k]))
    ans += sum(l)
print(ans)

### FIXED CODE ###

N = int(input())
s = [sorted(input()) for _ in range(N)]
s.sort()

cnt = 0
ans = 0
for i in range(N-1):
    if s[i] == s[i+1]:
        cnt +=1
        ans += cnt
    else:
        cnt = 0
print(ans)
### BUGGY CODE ###

 # -*- coding: utf-8 -*-
import sys

def main():
	N, W = map(int, input().split(" "))
	goods = []
	for _ in range(N):
		w, v = map(int, input().split(" "))
		goods.append((w, v))
		
	ans = 0
	for i in range(2 ** N):
		val = 0
		wal = 0
		for j in range(N):
			if i >> j & 1 == 1:
				w, v = goods[j]
				val += v
				wal += w
		if W < wal:
			continue
		if ans < val:
			ans = val
		
	print(ans)
		
if __name__ == "__main__":
	main()
	

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def main():
	N, W = map(int, input().split())
	wv = []
	for i in range(N):
		w, v = map(int, input().split())
		if w <= W:
			wv.append((w,v))
		
	DP = [[0 for _ in range(100001)] for _ in range(N)]
	
	for i, val in enumerate(wv):
		w, v = val
		if i == 0:
			DP[i][w] = v
			continue
			
		for j in range(W):
			DP[i][j] = max(DP[i-1][j], DP[i][j])
			
			if j+w <= W:
				DP[i][j+w] = max(DP[i-1][j] + v, DP[i][j+w])
			
	print(max(DP[N-1]))
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, H = MAP()
L = [LIST() for i in range(N)]

A = []
B = []
for a, b in L:
    A.append(a)
    B.append(b)

A.sort(reverse=True)
B.sort(reverse=True)

big_B = []

for b in B:
    if max(A) <= b:
        big_B.append(b)
thr = sum(big_B)
damage = 0 
cnt = 0

#
ruiseki_B = []

if thr >= H:
    cnt = len(big_B)
    not_need_damage = thr - H
    for i in range(len(big_B)):
        not_need_damage -= big_B[N-i-1]
        
        if not_need_damage <= 0:
            break
        else:
            cnt -= 1


    # for i in range(N):
    # while damage < H:
    #     damage += B[i]
    #     cnt += 1

    # i = 0
    # cnt = len(big_B)
    # while thr <= H:
    #     thr -= B[N-i-1]
    #     cnt -= 1

else:
    need_damage = H - thr
    cnt = len(big_B)
    if need_damage % A[0] == 0:
        cnt += need_damage // A[0]
    else:
        cnt += need_damage // A[0] + 1
print(cnt)

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, H = MAP()
L = [LIST() for i in range(N)]

A = []
B = []
for a, b in L:
    A.append(a)
    B.append(b)

A.sort(reverse=True)
B.sort(reverse=True)

big_B = []

ma_A = max(A)
for b in B:
    if ma_A <= b:
        big_B.append(b)
thr = sum(big_B)
damage = 0 
cnt = 0
if thr >= H:
    for i in range(N):
        if damage < H:
            damage += B[i]
            cnt += 1
else:
    need_damage = H - thr
    cnt = len(big_B)
    if need_damage % A[0] == 0:
        cnt += need_damage // A[0]
    else:
        cnt += need_damage // A[0] + 1
print(cnt)
### BUGGY CODE ###

n, m = map(int, input().split())

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

nums.sort(reverse=True)
for i in range(m):
    b, c = map(int, input().split())
    for j in range(n):
        if nums[j] < c:
            temp = nums[0:j]
            temp.extend([c]*b)
            temp.extend(nums[j:])
            nums = temp[0:n]
            break
        
result = 0
for i in nums:
    result = result + i

print(result)

### FIXED CODE ###

n, m = map(int, input().split())

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

ops = []
for i in nums:
    ops.append([1, i])
    
for i in range(m):
    b, c = map(int, input().split())
    ops.append([b, c])

total = 0
sums = []
for b, c in sorted(ops, key=lambda x:x[1], reverse=True):
    if total > n:
        break
    sums.extend([c]*b)
    total = total + b
print(sum(sums[:n]))
### BUGGY CODE ###

# coding: utf-8

N, Q = map(int, input().split())
S = input()

tile = {} # 文字マップ
now = [1] * N

for s in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
  tile.setdefault(s, [])

for i in range(len(S)):
  tile[S[i]].append(i)

for i in range(Q):
  t, d = input().split()
  if d == "L":
    for j in tile[t]:
      if j != 0:
        now[j-1] += now[j]
      now[j] = 0
  else:
    for j in tile[t]:
      if j != N-1:
        now[j+1] += now[j]
      now[j] = 0

print(sum(now))

### FIXED CODE ###

# coding: utf-8
import sys

input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()
td_list = [input().split() for _ in range(Q)]
dest = [-2] * (N+1)

def sim(i): # i番目のゴーレムの最終結果を得る
  idx = i
  if dest[i] != -2:
    return dest[i]
  for td in td_list:
    if idx == -1:
      dest[i] = -1
      return -1
    elif idx == N:
      dest[i] = N
      return N
    elif td[0] == S[idx]:
      if td[1] == "L":
        idx -= 1
      else:
        idx += 1
  dest[i] = idx
  return idx


# 左側の境界を探索
left, right = -1, N

while right - left != 1:
  mid = (left + right) // 2
  if sim(mid) == -1:
    left = mid
  else:
    right = mid

lb = right

# 右側の境界を探索
left, right = -1, N

while left+1 < right:
  mid = (left + right) // 2
  if sim(mid) == N:
    right = mid
  else:
    left = mid

rb = left

print(rb - lb + 1)
### BUGGY CODE ###

S = list(input())
Q = int(input())

Query = [list(input()) for i in range(Q)]

for i in range(Q):
    if Query[i][0] == "1":
        S.reverse()
    else:
        if Query[i][2] == "1":
            S.insert(0, Query[i][4])
        else:
            S.append(Query[i][4])

print("".join(S))


### FIXED CODE ###

from collections import deque

S = list(input())
Q = int(input())

S = deque(S)

Query = [list(input()) for i in range(Q)]

rev_cnt = 0

for i in range(Q):
    if Query[i][0] == "1":
        rev_cnt += 1
    else:
        if Query[i][2] == "1":
            if rev_cnt % 2 == 1:
                S.append(Query[i][4])
            else:
                S.appendleft(Query[i][4])
        else:
            if rev_cnt % 2 == 1:
                S.appendleft(Query[i][4])
            else:
                S.append(Query[i][4])

if rev_cnt % 2 == 1:
    while len(S) != 0:
        print(S.pop(), end="")
else:
    while len(S) != 0:
        print(S.popleft(), end="")


print()
### BUGGY CODE ###

import itertools
import collections

def num_divisors_table(n):
    table = [0] * (n + 1)
    
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1
    
    return table
N = int(input())
#N=10**7
#print(prime_factor(N,prime_factor_table(N)))
ans = 0
for i,d in enumerate(num_divisors_table(N)):
    ans += i*d
print(ans)
    #num_divisors_table(N)



### FIXED CODE ###

import itertools
import collections

def num_divisors_table(n):
    table = [0] * (n + 1)
    
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1
        table[i] *= i
    return table

N = int(input())
#N=10**7
#print(prime_factor(N,prime_factor_table(N)))
ans = 0
print(sum(num_divisors_table(N)))

    #num_divisors_table(N)
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
mod = 1000000007
dp = [0]*(N+1)
dp[0] = 1
for i in range(1, N+1):
    if i not in a:
        if i == 1:
            dp[i] = dp[i-1]
        else:
            dp[i] = (dp[i-1]+dp[i-2])%mod
print (dp[N])

### FIXED CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
a = set(a)
mod = 1000000007
dp = [0]*(N+1)
dp[0] = 1
for i in range(1, N+1):
    if i not in a:
        if i == 1:
            dp[i] = dp[i-1]
        else:
            dp[i] = (dp[i-1]+dp[i-2])%mod
print (dp[N])
### BUGGY CODE ###

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

c = 1
if p_list == [p_list[0]]*N:
    print(len(p_list))

elif p_list == sorted(p_list):
    print(1)

elif p_list == sorted(p_list, reverse=True):
    print(len(p_list))

else:
    for i in range(N):
        temp = 0
        for j in range(i):
            if p_list[i] <= p_list[j]:
                temp += 1
                if temp == i:
                    c += 1
            else:
                break
    print(c)
    #print("else")

### FIXED CODE ###

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

ans = 1
mi = p_list[0]

for i in range(1, N):
    if mi >= p_list[i]:
        ans += 1
        mi = p_list[i]
        
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC = [list(map(int,input().split())) for _ in range(Q)]
for i in range(Q):
  A = [BC[i][1] if j == BC[i][0] else j for j in A]
  print(sum(A))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC = [list(map(int,input().split())) for _ in range(Q)]
total = sum(A)
dict = {}
for i in range(len(A)):
  if A[i] not in dict:
    dict[A[i]] = 1
  else:
    dict[A[i]] += 1
for i in range(Q):
  if BC[i][0] not in dict:
    dict[BC[i][0]] = 0
  if BC[i][1] not in dict:
    dict[BC[i][1]] = 0
  if dict[BC[i][0]] > 0:
    num = (BC[i][1] - BC[i][0]) * (dict[BC[i][0]])
    total += num
  print(total)
  dict[BC[i][1]] += dict[BC[i][0]]
  dict[BC[i][0]] = 0
### BUGGY CODE ###

K=int(input())
S=input()
N=len(S)
mod=10**9+7

fact=[0]*(K+N)
fact[0]=fact[1]=1
for i in range(2,K+N):
    fact[i]=fact[i-1]*i%mod

def comb(n,r):
    ret=fact[n]*pow(fact[r],-1,mod)*pow(fact[n-r],-1,mod)%mod
    return ret

ans=0
for i in range(K+1):
    ans+=pow(26,i,mod)*pow(25,K-i,mod)*comb(K+N-1-i,N-1)
    ans%=mod

print(ans)

### FIXED CODE ###

K=int(input())
S=input()
N=len(S)
mod=10**9+7

fact=[0]*(K+N)
fact[0]=fact[1]=1
for i in range(2,K+N):
    fact[i]=fact[i-1]*i%mod

def comb(n,r):
    ret=fact[n]*pow(fact[r],mod-2,mod)*pow(fact[n-r],mod-2,mod)%mod
    return ret

ans=0
for i in range(K+1):
    ans+=pow(26,i,mod)*pow(25,K-i,mod)*comb(K+N-1-i,N-1)
    ans%=mod

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

s = list(input())
t = list(input())
q = int(input())

def check(x, y):
	xa = len(list(filter(lambda i: i == "A", x)))
	ya = len(list(filter(lambda i: i == "A", y)))
	if (2 * xa - len(x)) % 3 == (2 * ya - len(y)) % 3:
		print("YES")
	else:
		print("NO")

for _ in range(q):
	a, b, c, d = map(int, input().split())
	check(s[a - 1 : b], t[c - 1 : d])


### FIXED CODE ###

s = input()
t = input()
q = int(input())

sa_pre = [s[i] == "A" for i in range(len(s))]
ta_pre = [t[i] == "A" for i in range(len(t))]

sa = [0, sa_pre[0]]
ta = [0, ta_pre[0]]

for i in range(1, len(s)):
	sa.append(sa[-1] + sa_pre[i])

for i in range(1, len(t)):
	ta.append(ta[-1] + ta_pre[i])

def check(a, b, c, d):
	xa = sa[b] - sa[a - 1]
	ya = ta[d] - ta[c - 1]
	if (2 * xa - (b - a + 1)) % 3 == (2 * ya - (d - c + 1)) % 3:
		print("YES")
		return
	else:
		print("NO")
		return

for _ in range(q):
	a, b, c, d = map(int, input().split())
	check(a, b, c, d)
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
C = [10**13 for i in range(N)]
C[0] = 0
for i in range(N):
    for j in range(1, K+1):
        if i+j < N:
            C[i+j] = min(C[i] + abs(H[i+j]-H[i]), C[i+j])
print(C[-1])


### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
C = [10**13 for i in range(N)]
C[0] = 0
for i in range(N):
    for j in range(1, K+1):
        if i+j < N:
            C[i+j] = min(C[i] + abs(H[i+j]-H[i]), C[i+j])
print(C[-1])