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

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

l=[]
for _ in range(Q):
    l.append(list(map(int,input().split())))

t = [0]*(N+1)
for i in range(len(S)-1):
    if S[i] == 'A' and S[i+1] == 'C':
        t[i+1] = 1

for j in range(len(l)):
    print(sum(t[l[j][0]:l[j][1]]))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
t = [0]*(N+1)
for i in range(len(S)-1):
    if S[i] == 'A' and S[i+1] == 'C':
        t[i+1] = 1

import numpy
res = numpy.cumsum(t)

for _ in range(Q):
    l=list(map(int,input().split()))
    print(res[l[1]-1]-res[l[0]-1])
### BUGGY CODE ###

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


Query=[]
answer=[[0]*N for i in range(N)]
for i in range(M):
  L,R=map(int,input().split())
  for j in range(1,L+1):
    for k in range(R,N+1):
      answer[j-1][k-1]+=1

for i in range(Q):
  p,q=map(int,input().split())
  print(answer[p-1][q-1])

### FIXED CODE ###

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


Query=[]
answer=[[0]*N for i in range(N)]
for i in range(M):
  L,R=map(int,input().split())
  answer[N-L][R-1]+=1

for i in range(1,N):
  answer[0][i]+=answer[0][i-1]
  answer[i][0]+=answer[i-1][0]
  
for i in range(1,N):
  for j in range(1,N):
    answer[i][j]+=answer[i-1][j]
    answer[i][j]+=answer[i][j-1]
    answer[i][j]-=answer[i-1][j-1]
for i in range(Q):
  p,q=map(int,input().split())
  print(answer[N-p][q-1])
'''
for i in range(Q):
  answer=0
  Query=list(map(int,input().split()))
  for j in range(M):
    if train[j][0]>=Query[0] and train[j][1]<=Query[1]:
      answer+=1
  print(answer)
'''
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces

n, K = na()


eqi = [0 for i in range(K)]#eqi[i] = (gcd(A_1,A_2,...,A_N) = i となる組の数)

for i in range(K,0,-1):
    if i == 1:
        eqi[i-1] = K**n - sum(eqi)
        break
    #A_1,A_2,...,A_Nのすべてがiの倍数になる組の数
    tmp = (K//i)**n
    #A_1,A_2,...,A_Nのすべてがm*iの倍数になる組の数を引く(n = {2,3,4,...})
    for m in range(2,(K//i)+1):
        tmp -= eqi[m*i - 1]
    eqi[i-1] = tmp%(10**9 + 7)
ans = 0
for i in range(K):
    ans += ((i+1)*eqi[i])%(10**9 + 7)
print(ans%(10**9 + 7))


### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces

n, K = na()
mod = 1000000007

#n乗に**nを使うとTLEになる.powを使いましょう
eqi = [pow(K//(i+1), n, mod) for i in range(K)]#eqi[i] = (gcd(A_1,A_2,...,A_N) = i となる組の数)

for i in range(K,0,-1):
    if i == 1:
        eqi[i-1] -= sum(eqi[1:])
        break
    #A_1,A_2,...,A_Nのすべてがiの倍数になる組の数
    #tmp = (K//i)**n
    #A_1,A_2,...,A_Nのすべてがm*iの倍数になる組の数を引く(n = {2,3,4,...})
    for m in range(2,(K//i)+1):
        eqi[i-1] -= eqi[m*i - 1]
    eqi[i-1] %= mod
ans = 0
for i in range(K):
    ans += ((i+1)*eqi[i])%mod
print(ans%mod)
### BUGGY CODE ###

N=int(input())
number=list(map(int,input().split()))
MOD = 10**9+7
sum=0
for i in range(N-1):
    for j in range(i+1,N):
        sum=(sum+((number[i]*number[j]%MOD)))%MOD
print(sum)

### FIXED CODE ###

N=int(input())
number=list(map(int,input().split()))
MOD = 10**9+7
sum=sum(number)
s=sum%MOD
ans=0
for i in number:
    s-=i
    s%=MOD
    ans+=s*i
    ans%=MOD
print(ans)
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
t = sorted(x)
for i in range(n):
    j = t.index(x[i])
    s = t[:j] + t[j + 1:]
    print(s[n // 2 - 1])

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
t = sorted(x)
mid1, mid2 = t[n // 2 - 1], t[n // 2]
for i in range(n):
    if x[i] <= mid1:
        print(mid2)
    else:
        print(mid1)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
for i in a:
  b.append(i)
  b.reverse()
outp=str(b[0])
for i in range(1,n):outp+=" "+str(b[i])
print(outp)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=a[::-2]
if(n%2==1):c=a[1::2]
else:c=a[::2]
#print(b)
#print(c)
outp=str(b[0])
for i in range(1,len(b)):outp+=" "+str(b[i])
for i in range(len(c)):outp+=" "+str(c[i])
print(outp)
### BUGGY CODE ###

import sys
def input():return sys.stdin.readline().strip()
S=input()
Q=int(input())
for i in range(Q):
    q=input()
    if q=='1':
        S=S[::-1]
    else:
        a,f,c=q.split()
        S=''.join((c,S)) if f=='1' else ''.join((S,c)) 
print(S)

### FIXED CODE ###

S=input()
b=1
x=''
y=''
for i in range(int(input())):
    q=input()
    if q=='1':b^=1
    else:
        a,f,c=q.split()
        if (int(f)-1)^b:x=c+x
        else:y=y+c
S=x+S+y
print(S if b else S[::-1])
### BUGGY CODE ###

n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort()
for _ in range(n):
    if len(a)<2:
        break
    else:
        bi=format(a[-1], 'b')
        x=2**len(bi)-a[-1]
        if x==a[-1] and a.count(x)>1:
            ans+=1
            a.remove(x)
            a.remove(x)
            continue
        elif x in a and x!=a[-1]:
            ans+=1
            a.remove(x)
        a.pop()
print(ans)

### FIXED CODE ###

import collections
import bisect
n= int(input())
a=list(map(int, input().split()))
c=collections.Counter(a)
ans=0
des=sorted(a,reverse=True)
# asc=sorted(a)

for i in des:
    if c[i]>0:
        bi=format(i, 'b')
        x=2**len(bi)-i
        c[i]-=1
        if c[x]>0:
            c[x]-=1
            ans+=1
print(ans)
### BUGGY CODE ###

import sys
import math
import bisect

def query_gcd(a, b):
    if b == 0:
        return a
    return query_gcd(b, a % b)

def query_gcd_3(a, b, c):
    return query_gcd(query_gcd(a, b), c)

def main():
    n = int(input())
    ans = 0
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            for k in range(1, n + 1):
                ans += query_gcd_3(i, j, k)
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import math
import bisect

d = dict()

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def build_table():
    global d
    for i in range(1, 201):
        for j in range(1, 201):
            d[(i, j)] = gcd(i, j)

def query_gcd_3(a, b, c):
    g = d[(a, b)]
    return d[(g, c)]

def main():
    build_table()
    n = int(input())
    ans = 0
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            for k in range(1, n + 1):
                ans += query_gcd_3(i, j, k)
    print(ans)

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

# -*- coding: utf-8 -*-
n = int(raw_input())
s = str(raw_input())

ans=[]
for i in xrange(0,n):
    ans.append(-1)
ans[0]=0

for i in xrange(1,n):
    if s[i] == ".":
        ans[i] = min(s[:i].count("#"), ans[i-1]+1)
    else:
        ans[i] = min(ans[i-1], s[:i].count("#")+1)

print ans[n-1]


### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(raw_input())
s = str(raw_input())

ans=[]
black=[]
for i in range(0,n):
    ans.append(-1)
    black.append(-1)
ans[0]=0
if s[0]==".":
    black[0]=0
else:
    black[0]=1

for i in range(1,n):
    if s[i] == ".":
        black[i] = black[i-1]
        ans[i] = min(black[i-1], ans[i-1]+1)
    else:
        black[i] = black[i-1] + 1
        ans[i] = min(ans[i-1], black[i-1]+1)

print ans[n-1]
### BUGGY CODE ###

h, w = map(int, input().split())
grid = []
bias_inf = 2000
for i in range(h):
    k = list(map(int, input().split()))
    grid.append(k)
for i in range(h):
    k = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - k[j])

dp = [[[False for i in range(-bias_inf,bias_inf)] for j in range(w)] for k in range(h)]
dp[0][0][0 - grid[0][0]] = True
dp[0][0][0 + grid[0][0]] = True
for i in range(h):
    for j in range(w):
        for k in range(-bias_inf,bias_inf):
            if i == h-1 and j == w-1:
                break
            if dp[i][j][k]:
                if i == h-1:
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i][j+1][k + grid[i][j+1]] = True
                elif j == w-1:
                    dp[i+1][j][k - grid[i+1][j]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                else:
                    dp[i][j+1][k + grid[i][j+1]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i+1][j][k - grid[i+1][j]] = True
ans = bias_inf
for i in range(-bias_inf,bias_inf):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
bias_inf = 2000
for i in range(h):
    k = list(map(int, input().split()))
    grid.append(k)
for i in range(h):
    k = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - k[j])

dp = [[[0 for i in range(-bias_inf,bias_inf)] for j in range(w)] for k in range(h)]
dp[0][0][0 - grid[0][0]] = 1
dp[0][0][0 + grid[0][0]] = 1
for i in range(h):
    for j in range(w):
        for k in range(-bias_inf,bias_inf):
            if i == h-1 and j == w-1:
                break
            if dp[i][j][k]:
                if i != h-1 and j != w-1:
                    dp[i][j+1][k + grid[i][j+1]] = 1
                    dp[i+1][j][k + grid[i+1][j]] = 1
                    dp[i][j+1][k - grid[i][j+1]] = 1
                    dp[i+1][j][k - grid[i+1][j]] = 1
                elif j == w-1:
                    dp[i+1][j][k - grid[i+1][j]] = 1
                    dp[i+1][j][k + grid[i+1][j]] = 1
                else:
                    dp[i][j+1][k - grid[i][j+1]] = 1
                    dp[i][j+1][k + grid[i][j+1]] = 1
ans = bias_inf
for i in range(-bias_inf,bias_inf):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))
print(ans)
### BUGGY CODE ###

from collections import deque

h,w=map(int,input().split())

maze=[list(input()) for i in range(h)]

ans=0

dx=[1,-1,0,0]
dy=[0,0,1,-1]


for i in range(h):
  for j in range(w):
    for ii in range(h):
      for jj in range(w):
        Q=deque()
        Q.append((i,j,0))
        
        if maze[i][j]=='#' or maze[ii][jj]=='#':
          continue

        dp=[[False]*w for b in range(h)]

        while Q:
          p=Q.popleft()
          if p[0]==ii and p[1]==jj:
            ans=max(ans,p[2])
            break
          for k in range(4):
            nx=p[0]+dx[k]
            ny=p[1]+dy[k]

            if 0<=nx<h and 0<=ny<w and maze[nx][ny]=='.' and dp[nx][ny]==False:
              Q.append((nx,ny,p[2]+1))
              dp[nx][ny]=True


print(ans)

### FIXED CODE ###

from collections import deque

h,w=map(int,input().split())

maze=[list(input()) for i in range(h)]

ans=0

dx=[1,-1,0,0]
dy=[0,0,1,-1]


for i in range(h):
  for j in range(w):
        Q=deque()
        Q.append((i,j,0))
        
        if maze[i][j]=='#':
          continue

        dp=[[-1]*w for i in range(h)]

        dp[i][j]=0

        while Q:
          p=Q.popleft()
          ans=max(ans,p[2])
          for k in range(4):
            nx=p[0]+dx[k]
            ny=p[1]+dy[k]

            if 0<=nx<h and 0<=ny<w and maze[nx][ny]=='.' and dp[nx][ny]==-1:
              Q.append((nx,ny,p[2]+1))
              dp[nx][ny]=p[2]+1


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

N=int(input())
A=list(map(int,input().split()))
dic={}
for i in set(A):
  dic[i]=A.count(i) 

c=0
for i in dic.values():
  c+=i*(i-1)/2
for j in range(1,N+1):
  d=c-dic[A[j-1]]+1
  print(int(d))
  

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
dic={}
for a in A:
  if a in dic:
    dic[a]+=1
  else:
    dic[a]=1
   

c=0
for i in dic.values():
  c+=i*(i-1)/2
for j in range(1,N+1):
  d=c-dic[A[j-1]]+1
  print(int(d))
### BUGGY CODE ###

n,k=map(int,input().split())
s=[]
count=0
for i in range(n+1):
  count+=i
  s.append(count)

t=[]
for i in range(n+1):
  tmp=0
  for j in range(i+1):
    tmp+=n-j
  t.append(tmp)

ans=0
for i in range(k-1,n+1):
  ans+=t[i]-s[i]+1
  ans%=(10**9+7)

print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
s=[]
count=0
for i in range(n+1):
  count+=i
  s.append(count)

t=[n]
tmp=n
for i in range(1,n+1):
  tmp-=1
  t.append(t[i-1]+tmp)
# print(t)

ans=0
for i in range(k-1,n+1):
  ans+=t[i]-s[i]+1
  ans%=(10**9+7)

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

num = int(input())
array = [int(x) for x in input().split()]

res = []
for i in range(0, num):
    if i % 2 == 0:
        res.append(array[i])
    else:
        res.insert(0, array[i])

if num % 2 == 0:
    res = map(str, res)
    print(" ".join(res))
else:
    res = map(str, res[::-1])
    print(" ".join(res))


### FIXED CODE ###

import math

num = int(input())
array = [int(x) for x in input().split()]

zero_array = array[0::2]
one_array = array[1::2]

if num % 2 == 0:
    one_array = one_array[:int(num/2)]
    pick = one_array[::-1] + zero_array[:int(num/2)]
else:
    one_array = one_array[:int(num/2)]
    pick= one_array[::-1] + zero_array[:math.ceil(num/2)]

if num % 2 == 0:
    print(" ".join(map(str, pick)))
else:
    print(" ".join(map(str, pick[::-1])))
### BUGGY CODE ###

N = int(input())
S = input()
dp = {}
for i in range(N-2):
  for j in range(i+1, N-1):
    if dp.get(S[i] + S[j], 0) > 0:
      continue
    dp[S[i] + S[j]] = len(set([S[k] for k in range(j+1, N)]))
print(sum(dp.values()))

### FIXED CODE ###

N = int(input())
S = input()
dp = {}
si = set()
for i in range(N-2):
  if S[i] in si:
    continue
  si.add(S[i])
  for j in range(i+1, N-1):
    if dp.get(S[i] + S[j], 0) > 0:
      continue
    dp[S[i] + S[j]] = len(set(S[j+1:]))
print(sum(dp.values()))
### BUGGY CODE ###

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

import sys
from collections import Counter

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

def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    # 終点はルート切り捨て+1
    for i in range(2, int(sqrt(num))+1):
        # 素因数分解：小さい方から割れるだけ割って素数をカウント
        while num % i == 0:
            num //= i
            d[i] += 1
        # 1まで分解したら終了
        if num == 1:
            break
    # 最後に残ったnumは素数(ただし1^1は1^0なので数に入れない)
    if num != 1:
        d[num] += 1
    return d

def mul(C1, C2):
    return C1 + C2

def div(C1, C2):
    return C1 - C2

def gcd(C1, C2):
    return C1 & C2

def lcm(C1, C2):
    res = C1.copy()
    for k, v in C2.items():
        res[k] = max(C1[k], v)
    return res
    # return C1 | C2

N = INT()
A = LIST()

# 素因数の状態で全体のLCMを出す
A2 = [factorize(a) for a in A]
l2 = Counter()
for a in A2:
    l2 = lcm(l2, a)

# 通常の値に戻す
l = 1
for k, v in l2.items():
    l *= pow(k, v, MOD)
    l %= MOD

ans = 0
for a in A:
    ans += fermat(l, a, MOD)
    ans %= MOD
print(ans)


### FIXED CODE ###

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

import sys
from fractions import gcd

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

def lcm(x, y): return (x * y) // gcd(x, y)

N = INT()
A = LIST()

l = 1
for a in A:
    l = lcm(l, a)

ans = 0
for i, a in enumerate(A):
    ans += l // a
print(ans%MOD)
### BUGGY CODE ###

# coding: utf-8
 
# 標準入力 <int>
N = int(input())
 
# 標準入力<str>
S = input()
 
ans = 0
 
for i in range(N - 2):
  S2 = []
  for j in range(N - i - 2):
    if S[i] == S[i + j + 1]:
      continue
    if i + ((j + 1) * 2) < N:
      S2 = S[i + j + 2:i + (2 * j) + 2] + S[i + (2 * j) + 3:]
    else:
      S2 = S[i + j + 2:]
    S2 = S2.replace(S[i], "")
    S2 = S2.replace(S[i + j + 1], "")
    ans += len(S2)
 
print(ans)

### FIXED CODE ###

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力<str>
S = input()

R = S.count("R")
G = S.count("G")
B = S.count("B")

cnt = 0

for i in range(N - 2):
  for j in range(i + 1, N - 1):
    k = i + ((j - i) * 2)
    if k < N:
      if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
        cnt += 1

print(R * G * B - cnt)
### BUGGY CODE ###

H, W = [int(x) for x in input().split(" ")]


class Node:
    def __init__(self, text, pos):
        self.text = text
        self.pos = pos
        self.next_nodes = []

    def add_next(self, node):
        self.next_nodes.append(node)


nodes = dict()
for i in range(H):
    for j, text in enumerate(input()):
        nodes[(i, j)] = Node(text, (i, j))


for i in range(H):
    for j in range(W):
        node = nodes[(i, j)]
        if node.text == "#":
            continue
        for pos in [(i-1, j), (i, j-1), (i+1, j), (i, j+1)]:
            if 0 <= pos[0] <= H-1 and 0 <= pos[1] <= W-1 and nodes[pos].text == ".":
                node.add_next(nodes[pos])


def all_pats():
    pat = []
    for i in range(H):
        for j in range(W):
            pat.append((i, j))
    return pat


def search(start, end):
    queue = []
    queue.append(start)
    count = dict()
    count[start.pos] = 0

    while True:
        if not queue:
            break
        node = queue[0]
        if node.pos == end:
            break
        queue = queue[1:]

        for next_node in node.next_nodes:
            if next_node.pos in count:
                continue
            count[next_node.pos] = count[node.pos] + 1
            queue.append(next_node)
    return count[end.pos]


total = []
searched = []
for start in all_pats():
    for end in all_pats():
        if (start, end) in searched:
            continue
        start_node = nodes[start]
        end_node = nodes[end]
        if start_node.text == "." and end_node.text == ".":
            res = search(start_node, end_node)
            total.append(res)
        searched.append((start, end))

print(max(total))


### FIXED CODE ###

class Node:
    def __init__(self, text, pos):
        self.text = text
        self.pos = pos
        self.next_nodes = []

    def add_next(self, node):
        self.next_nodes.append(node)


def all_pats():
    pat = []
    for i in range(H):
        for j in range(W):
            pat.append((i, j))
    return pat


def dfs(start):
    queue = []
    queue.append(start)
    count = dict()
    count[start.pos] = 0

    while True:
        if not queue:
            break
        node = queue[0]
        queue = queue[1:]

        for next_node in node.next_nodes:
            if next_node.pos in count:
                continue
            count[next_node.pos] = count[node.pos] + 1
            queue.append(next_node)
    return max(count.values())


H, W = [int(x) for x in input().split(" ")]
nodes = dict()
for i in range(H):
    for j, text in enumerate(input()):
        nodes[(i, j)] = Node(text, (i, j))


for i in range(H):
    for j in range(W):
        node = nodes[(i, j)]
        if node.text == "#":
            continue
        for pos in [(i-1, j), (i, j-1), (i+1, j), (i, j+1)]:
            if 0 <= pos[0] <= H-1 and 0 <= pos[1] <= W-1 and nodes[pos].text == ".":
                node.add_next(nodes[pos])


all_pats = all_pats()

counts = []
for start in all_pats:
    counts.append(dfs(nodes[start]))

print(max(counts))
### BUGGY CODE ###

import sys
import numpy as np
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,T=map(int,input().split())
    A=[0]*N
    B=[0]*N
    for i in range(N):
        A[i],B[i]=map(int,input().split())
    A_argsorted=np.argsort(A)
    dp=[[0]*T for _ in range(N)]
    for i in range(N-1):
        for t in range(T-1):
            dp[i+1][t+1]=max(dp[i+1][t+1],dp[i][t+1])
            if t+1>=A[A_argsorted[i]]:
                dp[i+1][t+1]=max(dp[i+1][t+1],dp[i][t+1-A[A_argsorted[i]]]+B[A_argsorted[i]])
    ans=0
    B_sorted=[B[x] for x in A_argsorted]
    for i in range(1,N):
        ans=max(ans,dp[i][T-1]+max(B_sorted[i:]))
    print(ans)
        

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,T=map(int,input().split())
    l=[]
    for i in range(N):
        A,B=map(int,input().split())
        l.append((A,B))
    l.sort()
    dp=[[0]*T for _ in range(N)]
    for i in range(N-1):
        for t in range(T-1):
            dp[i+1][t+1]=max(dp[i+1][t+1],dp[i][t+1])
            if t+1>=l[i][0]:
                dp[i+1][t+1]=max(dp[i+1][t+1],dp[i][t+1-l[i][0]]+l[i][1])
    ans=0
    B_sorted=[x[1] for x in l]
    for i in range(1,N):
        ans=max(ans,dp[i][T-1]+max(B_sorted[i:]))
    print(ans)
        

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

a = list(map(int,input().split()))
 
b = [[] for i in range(a[0])]
 
c = [0 for i in range(a[2])]
 
co = 0
for i in range(a[1]):
    n,m = map(int,input().split())
 
    b[m-1].append(n)
  
for i in range(len(b)):
    b[i].sort()
    
for i in range(a[2]):
    n,m = map(int,input().split())
    for j in range(n-1,m):
        for k in range(len(b[j])):
            if b[j][k] >= n:
                co += 1
    print(co)
    co = 0

### FIXED CODE ###

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

c = [[0 for i in range(a[0]+1)] for j in range(a[0]+1)]

for i in range(a[1]):
    n,m = map(int,input().split())
    c[n][m] += 1

d = [[0 for i in range(a[0]+4)] for j in range(a[0]+4)]

for i in range(a[0]+1):
    for j in range(a[0]+1):
        d[i][j+1] = d[i][j] + c[i][j]

for i in range(a[2]):
    n,m = map(int,input().split())
    s = 0
    for j in range(n,m+1):
        s += d[j][m+1] - d[j][j]
    print(s)
### BUGGY CODE ###

s=input()
l=len(s)
mod = pow(10,9)+7

dp = [[0 for i in range(13)] for j in range(l+1)]
dp[0][0] = 1

for i in range(1,l+1):
	num = s[-i]
	keta = pow(10,i-1)
	if num == '?':
		for j in range(10):
			tmp = ( int(j) * keta ) % 13
			for k in range(13):
				index = (tmp + k) % 13
				dp[i][index] += dp[i-1][k]
				dp[i][index] %= mod
	else:
		tmp = ( int(num) * keta ) % 13
		for k in range(13):
			index = (tmp + k) % 13
			dp[i][index] += dp[i-1][k]
			dp[i][index] %= mod
print(dp[l][5] % mod)


### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

inf = float("inf") # 正の無限大

def chmin(dp, n, a):
	b = (dp[n]>a)
	if b: dp[n]=a
	return b


N,K=map(int, input().split())
H=[0]+list(map(int, input().split()))
#print(N,H)

dp=[inf]*(N+1)
dp[1]=0
dp[2]=abs(H[2]-H[1])

for i in range(3,N+1):
	for k in range(1,K+1):
		if (i-k)>0: chmin(dp, i, dp[i-k]+abs(H[i]-H[i-k]))

print( dp[N] )






### FIXED CODE ###

inf = float("inf") # 正の無限大

N,K=map(int, input().split())
H=[0]+list(map(int, input().split()))
#print(N,H)

dp=[inf]*(N+1)
dp[1]=0
dp[2]=abs(H[2]-H[1])

for i in range(3,N+1):
	for k in range(1,K+1):
		if (i-k)>0:
			a = dp[i-k]+abs(H[i]-H[i-k])
			if dp[i]>a: dp[i]=a

print( dp[N] )