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

import sys
input=sys.stdin.readline
n=int(input())
l=input()
q=int(input())
kl=tuple(map(int,input().split()))
for i in kl:
    k=i
    d=0
    m=0
    dm=0
    ans=0
    j=0
    for lj in l:
        if lj=='D':
            d+=1
        elif lj=='M':
            m+=1
            dm+=d
        elif lj=='C':
            ans+=dm
        if j>=k-1:
            if l[j-k+1]=='D':
                dm-=m
                d-=1
            if l[j-k+1]=='M':
                m-=1
        j+=1
    print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
l=input()
q=int(input())
kl=tuple(map(int,input().split()))
for k in kl:
    d=0
    m=0
    dm=0
    ans=0
    for j in range(n):
        if l[j]=='D':
            d+=1
        elif l[j]=='M':
            m+=1
            dm+=d
        elif l[j]=='C':
            ans+=dm
        if j>=k-1:
            if l[j-k+1]=='D':
                dm-=m
                d-=1
            elif l[j-k+1]=='M':
                m-=1
    print(ans)
### BUGGY CODE ###

from collections import deque


def main():
    """
    ゲームの開始時点ではマス (1,1)
    上下左右の 4 方向のいずれかに 1 マスだけ動かすことを繰り返す
    白いマスだけを通って (H,W) にたどり着けばゲームクリア

    マス (i,j) 最初
    白で塗られている場合 .
    黒で塗られている場合 #

    いくつかの白いマス目の色を黒に変えることができる
    ただし, マス (1,1) と (H,W) の色を変えることはできず
    -> ルートの変更は不可能

    ゲームをクリアしたとき, ゲームの開始前にマスの色を変えた回数がすぬけ君のスコアとなる
    最大のスコアを求めなさい
    → 最短距離を求め,必要ない白マスを黒に変えれば高スコア(BFS?)
    → 経路を覚えておかないといけない
    """
    H, W = map(int, input().split())
    S = [
        input()
        for _ in range(H)
    ]

    bfs(S, H, W)


def bfs(S, H, W):
    if S[0][0] == "#":
        print(-1)
        return

    n_pos = [(0, 1), (1, 0)]
    # 距離を追加, 経路情報は必要ない
    q = deque([(0, 1, 1), (1, 0, 1)])
    visited = [
        [False] * W
        for _ in range(H)
    ]
    visited[0][0] = True

    goal = False
    dist = 0
    while q:
        x, y, dist = q.pop()
        visited[y][x] = True
        if S[y][x] == "#":
            continue

        if (x, y) == (W-1, H-1):
            goal = True
            break

        for dx in (-1, 1):
            nx = x+dx
            if 0 <= nx < W:
                if S[y][nx] == "." and not visited[y][nx]:
                    q.appendleft((nx, y, dist+1))
        for dy in (-1, 1):
            ny = y+dy
            if 0 <= ny < H:
                if S[ny][x] == "." and not visited[ny][x]:
                    q.appendleft((x, ny, dist+1))

    if goal:
        w_count = 0
        for s in S:
            w_count += s.count(".")
        # startは通ってないので距離に含まれない
        print(w_count - dist - 1)
    else:
        print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque


def main():
    """
    ゲームの開始時点ではマス (1,1)
    上下左右の 4 方向のいずれかに 1 マスだけ動かすことを繰り返す
    白いマスだけを通って (H,W) にたどり着けばゲームクリア

    マス (i,j) 最初
    白で塗られている場合 .
    黒で塗られている場合 #

    いくつかの白いマス目の色を黒に変えることができる
    ただし, マス (1,1) と (H,W) の色を変えることはできず
    -> ルートの変更は不可能

    ゲームをクリアしたとき, ゲームの開始前にマスの色を変えた回数がすぬけ君のスコアとなる
    最大のスコアを求めなさい
    → 最短距離を求め,必要ない白マスを黒に変えれば高スコア(BFS?)
    → 経路を覚えておかないといけない
    """
    H, W = map(int, input().split())
    S = [
        input()
        for _ in range(H)
    ]

    bfs(S, H, W)


def bfs(S, H, W):
    # 距離を追加, 経路情報は必要ない
    q = deque([(0, 0, 0)])
    visited = [
        [False] * W
        for _ in range(H)
    ]
    visited[0][0] = True

    goal = False
    dist = 0
    while q:
        x, y, dist = q.popleft()
        if (x, y) == (W-1, H-1):
            goal = True
            break

        for dx in (-1, 1):
            nx = x+dx
            if 0 <= nx < W:
                if S[y][nx] == "." and not visited[y][nx]:
                    q.append((nx, y, dist+1))
                    visited[y][nx] = True
        for dy in (-1, 1):
            ny = y+dy
            if 0 <= ny < H:
                if S[ny][x] == "." and not visited[ny][x]:
                    q.append((x, ny, dist+1))
                    visited[ny][x] = True

    if goal:
        w_count = 0
        for s in S:
            w_count += s.count(".")
        # startは通ってないので距離に含まれない
        print(w_count - dist - 1)
    else:
        print(-1)


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

import numpy as np
import copy
N,K = map(int, input().split())

A_list = [0]+list(map(int, input().split()))
A_np=np.array(A_list)
#print(A_np)

for j in range(K):
  new_A_np=np.array([0]*(N+1))
  for i in range(1,N+1):
    tmp_np=np.array([0]*(N+1))
    #print(A_np)
    mi=i-A_np[i]
    ma=i+A_np[i]
    if mi<0:
      mi=0
    if ma>N:
      ma=N
    #print(mi,ma)
    tmp_np[mi:ma+1]=1
    #print(tmp_np)
    new_A_np+=tmp_np
  #print(new_A_np)
  A_np=new_A_np.copy()

for i in range(1,N+1):
  print(A_np[i],end=" ")

### FIXED CODE ###

import numpy as np
from numba import njit

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

A_list = np.array([0]+list(map(int, input().split())))

@njit
def update(A_list):

  for j in range(min(K,46)):
    new_A=np.zeros(N+2,dtype=np.int64)
    for i in range(1,N+1):
      #print(new_A)
      mi=i-A_list[i]
      ma=i+A_list[i]
      if mi<0:
        mi=0
      if ma>N:
        ma=N
      #new_A[mi:ma+1]+=1
      new_A[mi]+=1
      new_A[ma+1]-=1

    A_list=np.cumsum(new_A)
    #if sum(A_list[1:N+1])==N*N:
    #  return(A_list)    
    #  break
      
  return(A_list)

A_list=update(A_list)
for i in range(1,N+1):
  print(A_list[i],end=" ")
### BUGGY CODE ###

# encoding:utf-8

def main():
	N = int(input())
	cards = list(map(int, input().split()))
	sum_cards = sum(cards)
	if N == 2:
		print(abs(cards[0] - cards[1]))
	else:
		out = min([abs(sum_cards - 2 * sum(cards[0:i])) for i in range(1, N-1)])
		print(out)

if __name__ == '__main__':
	main()

### FIXED CODE ###

# encoding:utf-8

def main():
	N = int(input())
	cards = list(map(int, input().split()))

	x = cards[0]
	y = sum(cards[1:])
	i = 1
	val = abs(x - y)

	while i < len(cards) - 1:
		x += cards[i]
		y += -cards[i]
		temp = abs(x - y)
		
		if temp == 0:
			val = 0
			break
		if temp < val:
			val = temp

		i += 1

	print(val)

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

N = int(input())
A = [int(x) for x in input().split()]

pair = []
unpair = []
for a in A:
    if a in unpair:
        pair.append(a)
        unpair.remove(a)
    else:
        unpair.append(a)

pair.sort()
pair.reverse()
if len(pair) <= 1:
    ans = 0
else:
    ans = pair[0] * pair[1]
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]

pair = []
unpair = set()
for a in A:
    if a in unpair:
        pair.append(a)
        unpair.remove(a)
    else:
        unpair.add(a)

pair.sort()
pair.reverse()
if len(pair) <= 1:
    ans = 0
else:
    ans = pair[0] * pair[1]
print(ans)
### BUGGY CODE ###

#import numpy as np

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]

for i in range(n):
    for j in range(n-1):
        A[i][j] -= 1

#print(A)

S = [0 for i in range(n)]
#F = [[0 for i in range(n)] for j in range(2*n*n)]

n1n = n*(n-1)
maxga = n//2

d = 0
for ii in range(n*n*2):
    F = [0 for i in range(n)]
    co = 0
    i = 0
    ga = 0
    for jj in range(n*n*2):
        si = S[i]
        if F[i] == 0 and si <= n-2:
            aite = A[i][si]
            #print(S)
            #print("aite",aite)
            if aite < n and A[aite][S[aite]] == i and F[aite] == 0:
                #print("g", i, aite)
                S[i] += 1
                S[aite] += 1
                F[i] = 1
                F[aite] = 1
                co = 0
                ga += 1
        i = (i+1) % n
        co += 1
        if co == n-1 or ga == maxga:
            break
    d += 1
    #print("d", d)
    if ga == 0:
        if sum(S) == n1n:
            print(d-1)
        else:
            print(-1)
        break



### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
    for j in range(n-1):
        A[i][j] -= 1

AA = [[j for j in i] for i in A]

ID = [[-1] * n for i in range(n)]
id_ = 0
for i in range(n):
    for j in range(i+1,n):
        ID[i][j] = id_
        ID[j][i] = id_
        id_ += 1

for i in range(n):
    for j in range(n-1):
        A[i][j] = ID[i][A[i][j]]

M = [[] for i in range(id_)]
IN = [0] * id_
for i in range(n):
    for j in range(n-2):
        M[A[i][j]].append(A[i][j+1])
        IN[A[i][j+1]] +=1
# print(A)
# print(M)

# 以下、トポロジカルソート

S = []
s = 0

for i in range(id_):
    if IN[i] == 0:
        S.append(i)

while s < len(S):
    for x in M[S[s]]:
        IN[x] -= 1
        # print(x,IN)
        if IN[x] == 0:
            S.append(x)
    s += 1

# print(S)

if len(S) < id_:
    print(-1)
else:
    T = [1] * id_
    for i in range(id_):
        for j in M[S[i]]:
            T[j] = max(T[j], T[S[i]] + 1)
    print(max(T))


# 以下、閉路検出(今は削除)

# V = [0] * id_
# S = [0]
# V[0] = 1

# import sys

# def visit(x):
#     if V[x] == 1:
#         print(-1)
#         sys.exit()
#     elif V[x] == 0:
#         V[x] = 1
#         for i in M[x]:
#             visit(i)
#         V[x] = 2

# for i in range(id_):
#     if V[i] == 0:
#         visit(i)
# print("heironasi")

# 閉路検出ここまで
### BUGGY CODE ###

k,s = map(int,input().split())
ans = 0
for i in range(0,k+1):
  for j in range(0,k+1):
    for l in range(0,k+1):
      if i + j + l == s:
        ans += 1
      else:
        continue
print(ans)

### FIXED CODE ###


k,s = map(int,input().split())
ans = 0
for i in range(k+1):
    for j in range(k+1):
        if k>=s-i-j>=0:
            ans +=1
        else:
            continue
print(ans)
### BUGGY CODE ###

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

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod



temp = cmb(X-1,X-1,mod)*power(26,K,mod)
temp %= mod

ans = temp

Y = 25*pow(26, mod-2, mod)

for i in range(X+1,K+X+1):
   
    temp *= Y
    temp %= mod
    
    temp *= i-1
    temp %= mod
    
    temp *= pow(i-X, mod-2, mod)
    temp %= mod    

    ans += temp
    ans %= mod

print(ans)

### FIXED CODE ###

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

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


A = 0
B = K
temp = cmb(A+X-1,X-1,mod)*power(25,A,mod)
temp %= mod
temp *= power(26,B,mod)
temp %= mod

ans = temp

for i in range(X+1,K+X+1):

    temp *= 25
    temp %= mod
    
    temp *= pow(26, mod-2, mod)
    temp %= mod
    
    temp *= i-1
    temp %= mod
    
    temp *= pow(i-X, mod-2, mod)
    temp %= mod    

    ans += temp
    ans %= mod

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

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

S = [1]
for i in range(0, N):
 S.append(S[i] * A[i])

count = 0
prev = -1
for i in range(K, N+1):
  current = S[i]//S[count]
  if prev != -1:
    if current > prev:
      print("Yes")
    else:
      print("No")
  prev = current
  count += 1 



### FIXED CODE ###

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

for i in range(N-K):
    print('Yes' if A[i] < A[i+K] else 'No')
### BUGGY CODE ###

import sys
from itertools import accumulate


def input():
    return sys.stdin.readline().strip()


MOD = 10 ** 9 + 7


def main():
    S = input()
    answer = 0
    for i in range(len(S)):
        func = lambda x, y: (int(x) * 10 + int(y)) % 2019
        A = list(accumulate(S[i:], func, initial=0))
        answer += A.count(0) - 1
    print(answer)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    S = list(input())
    N = len(S)
    check = [0] * 2019
    ten = 1
    mod = 1
    check[mod] += 1
    for i in range(N):
        mod = (mod + int(S[N - i - 1]) * ten) % 2019
        ten = (ten * 10) % 2019
        check[mod] += 1
    answer = 0
    for i in range(2019):
        answer += ((check[i] - 1) * check[i]) // 2
    print(answer)


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

from collections import defaultdict

N=int(input())
S=input()

c=defaultdict(int)
for i in range(N):
  c[S[i]] += 1
ans = c['R']*c['G']*c['B']

max_d = (N-3)//2+1

for d in range(1,max_d+1):
  for i in range(N-2):
    j,k = i+d,i+2*d
    if k > N-1:break
    if len(set([S[i],S[j],S[k]]))==3:
      ans -= 1
      
print(ans)

### FIXED CODE ###

from collections import Counter

N=int(input())
S=input()

c=Counter(S+'RGB')
ans = (c['R']-1)*(c['G']-1)*(c['B']-1)

max_d = (N-3)//2+1

for d in range(1,max_d+1):
  for i in range(N-2):
    j = i+d
    k = j+d
    if k > N-1:break
    if len(set([S[i],S[j],S[k]]))==3:
      ans -= 1
      
print(ans)
### BUGGY CODE ###

def main():
    n,x,d=map(int,input().split())
    s=set()
    for k in range(n+1):
        for j in range(k*(k-1)//2, 1+k*(2*n-k-1)//2):
            s.add(j*d+x*k)
    print(len(s))

if __name__=='__main__':
    main()


### FIXED CODE ###

import sys
from fractions import gcd
n, x, d = map(int, input().split())
if x == d == 0:
	print(1);sys.exit()
elif d == 0:
	print(n+1);sys.exit()
if x < 0 and x + (n-1) * d < 0:
	x, d = -x, -d
if x >= 0 and d < 0:
	x, d = x + (n-1) * d, -d
g = gcd(x, d);ans = 1
if x >= 0:
	for i in range(1, n+1):
		k = max((i- d//g) *(2*n -1 -i +d//g)//2 -x//g, i *(i-1) //2 -1)
		ans += max((i * (2*n-1-i)) //2 -k, 0)
else:
	for i in range(1, n+1):
		overlap_u = min((i -d//g) *(2*n -1 -i +d//g) //2 -x//g, i *(2*n-1-i) //2)
		overlap_l = max((i -d//g) *(i -d//g -1) //2 -x//g, i *(i-1) //2)
		ans += i *(2*n-1-i) //2 -i *(i-1) //2 +1 -max(overlap_u -overlap_l+1, 0)
print(ans)
### BUGGY CODE ###

import sys
from heapq import heappop, heappush

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1
    S = [input().strip("\n") for _ in range(H)]
    M = [[-1 for w in range(W)] for h in range(H)]
    move = ((-1, 0), (0, -1), (1, 0), (0, 1))
    q = []
    heappush(q, (0, ch, cw))
    while q:
        dist, h, w = heappop(q)
        if M[h][w] == -1:
            M[h][w] = dist
            for dh, dw in move:
                if 0<=h+dh<H and 0<=w+dw<W and S[h+dh][w+dw] == "." and M[h+dh][w+dw] == -1:
                    heappush(q, (dist, h+dh, w+dw))
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if 0<=h+dh<H and 0<=w+dw<W and S[h+dh][w+dw] == "." and M[h+dh][w+dw] == -1:
                        heappush(q, (dist + 1, h+dh, w+dw))
    print(M[fh][fw])


    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    sh, sw = map(int, input().split())
    sh -= 1
    sw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1

    S = [input().strip("\n") for _ in range(H)]

    q = deque()
    P = [[-1 for _ in range(W)] for h in range(H)]
    q.append((0, sh, sw))
    while q:
        d, h, w = q.popleft()
        if P[h][w] == -1:
            P[h][w] = d
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if 0<=h+dh<H and 0<=w+dw<W and S[h+dh][w+dw] == "." and P[h+dh][w+dw] == -1:
                        if abs(dh) + abs(dw) == 1:
                            q.appendleft((d, h+dh, w+dw))
                        else:
                            q.append((d+1, h+dh, w+dw))
    print(P[fh][fw])
    

    return 0

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

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

    if n <= k:
        print(0)
    else:
        for i in range(k):
            a.remove(max(a))

        print(sum(a))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, k = list(map(int, input().split()))
    h = list(map(int, input().split()))
    h = sorted(h, reverse=True)

    if n <= k:
        print(0)
    else:
        print(sum(h[k:]))


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

# -*- coding: utf-8 -*-
s = list(input())
q = int(input())

for i in range(q):
    query = input()
    if query == "1":
        s = s[::-1]
    else:
        x, q2_1, q2_2 = query.split()
        if q2_1 == "1":
            s.insert(0, q2_2)
        else:
            s.append(q2_2)
print("".join(s))

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import deque

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

a = deque(s)
reverse = False

for i in range(q):
    query = input()
    if query == "1":
        if reverse:
            reverse = False
        else:
            reverse = True
    else:
        x, q2_1, q2_2 = query.split()
        if q2_1 == "1":
            if reverse:
                a.append(q2_2)
            else:
                a.appendleft(q2_2)
        else:
            if reverse:
                a.appendleft(q2_2)
            else:
                a.append(q2_2)

s = list(a)
if reverse:
    s = s[::-1]
    print("".join(s))
else:
    print("".join(s))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
for i in a:
    b.append(i)
    b.reverse()
print(' '.join(map(str,b)))
    

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
c = []
for i in range(n):
    if  i % 2 == 1:
        b.append(a[i])
    else:
        c.append(a[i])
if n % 2 == 0:
    b.reverse()
    ans = b + c
else:
    c.reverse()
    ans = c + b
print(' '.join(map(str,ans)))
### BUGGY CODE ###

import math
n=int(input())
s=input()
d=dict()
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      d[s[i]+s[j]+s[k]]=0
print(len(d))

### FIXED CODE ###

n=int(input())
s=input()
ans=0
for i in range(1000):
  v=str(i)
  v=v.zfill(3)
  ss=s
  if not v[0] in ss:
    continue  
  ss=ss[ss.index(v[0])+1:]
  if not v[1] in ss:
    continue
  ss=ss[ss.index(v[1])+1:]
  if not v[2] in ss:
    continue
  ans+=1
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
X = int(input())
prime = [2]
if X == 2:
    print(2)
else:
    for i in range(2,X):
        c = 0
        for j in prime:
            if i % j == 0:
                c = 1
                break
        if c == 0:
            prime.append(i)
    for i in range(X,X + 1000):
        c = 0
        for j in prime:
            if i % j == 0:
                c = 1
                break
        if c == 0:
            print(i)
            break

### FIXED CODE ###

import sys
input=sys.stdin.readline
import math
X = int(input())
if X == 2:
    print(2)
else:
  x = math.ceil(math.sqrt(X))
  for i in range(X,X+1000):
      c = 0
      for j in range(2,x+1):
          if i % j == 0:
              c = 1
              break
      if c == 0:
          print(i)
          break
### BUGGY CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
# MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
# import numpy as np
# import operator
# import bisect
# from heapq import heapify,heappop,heappush
# from math import gcd
# from fractions import gcd
# from collections import deque
# from collections import defaultdict
# from collections import Counter
# from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())

def knapsack(N, W, weight, value):
	# 初期化
	inf = float("inf")
	dp = [[-inf for i in range(W + 1)] for j in range(N + 1)]
	for i in range(W + 1): dp[0][i] = 0
	
	# DP
	for i in range(N):
		for w in range(W + 1):
			if weight[i] <= w:  # dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
				dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i], dp[i][w])
			else:  # 入る可能性はない
				dp[i + 1][w] = dp[i][w]
	return dp


def main():
	n, t = map(int, input().split())
	AB = []
	A = []
	B = []
	for _ in range(n):
		a, b = map(int, input().split())
		AB.append((a, b))
	AB.sort()
	for a,b in AB:
		A.append(a)
		B.append(b)
	dp= knapsack(n, t, A, B)
	
	ans=0
	for i in range(n):
		ans=max(ans,dp[i][t-1] + AB[i][1])
	print(ans)


if __name__ == '__main__':
	main()


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
# MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
# import numpy as np
# import operator
# import bisect
# from heapq import heapify,heappop,heappush
# from math import gcd
# from fractions import gcd
# from collections import deque
# from collections import defaultdict
# from collections import Counter
# from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())

def knapsack(N, W, weight, value):
	# 初期化
	inf = float("inf")
	dp = [[-inf for i in range(W + 1)] for j in range(N + 1)]
	for i in range(W + 1): dp[0][i] = 0
	
	# DP
	for i in range(N):
		for w in range(W + 1):
			if weight[i] <= w:  # dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
				dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i], dp[i][w])
			else:  # 入る可能性はない
				dp[i + 1][w] = dp[i][w]
	return dp


def main():
	n, t = map(int, input().split())
	AB = []
	A = []
	B = []
	for _ in range(n):
		a, b = map(int, input().split())
		AB.append((a, b))
	AB.sort()
	for a,b in AB:
		A.append(a)
		B.append(b)
	dp= knapsack(n, t, A, B)
	
	ans=0
	for i in range(n):
		ans=max(ans,dp[i][t-1] + AB[i][1])
	print(ans)


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

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
b=[(True if i in a else False) for i in range(n+1)]
fib=[0]*(n+1)
fib[0]=1
fib[1]=[1,0][b[1]]
for i in range(2,n+1):
  fib[i]=[fib[i-1]+fib[i-2],0][b[i]]
  fib[i]%=10**9+7
print(fib[n])

### FIXED CODE ###

n,m=map(int,input().split())
mod=10**9+7
a=[False]*(n+1)
for i in range(m):
  a[int(input())]=True
fib=[0]*(n+1)
fib[0]=1
fib[1]=[1,0][a[1]]
for i in range(2,n+1):
  if a[i]:
    fib[i]=0
  else:
    fib[i]=(fib[i-1]+fib[i-2])%mod
print(fib[n])
### BUGGY CODE ###

import sys
msg = sys.stdin.readlines()
a = []
for x in msg:
  a.append(x.replace('\n', ''))
arra = a[1].split(' ')
dump = []
res = 'YES'
for x in range(int(a[0])):
  if arra[x] in dump:
    res = 'NO'
    break
  dump.append(arra[x])
print(res)



### FIXED CODE ###

import sys
msg = sys.stdin.readlines()
a = []
for x in msg:
  a.append(x.replace('\n', ''))
arra = a[1].split(' ')
arra = [int(x) for x in arra]
if len(arra) == len(set(arra)):
  print('YES')
else:
  print('NO')