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

import sys
finput = sys.stdin.readline

S = finput()

MOD = 10**9 + 7

# time complexity: O(|S|)
def dp(S):
    dp = [[0] * 4 for _ in range(len(S) + 1)]
    dp[len(S)][3] = 1
    for i in range(len(S))[::-1]:
        dp[i][3] = 3 * dp[i + 1][3] if S[i] == "?" else dp[i + 1][3]
        dp[i][3] %= MOD
        if S[i] == "?":
            dp[i][0] = (3 * dp[i + 1][0] + dp[i + 1][1]) % MOD
            dp[i][1] = (3 * dp[i + 1][1] + dp[i + 1][2]) % MOD
            dp[i][2] = (3 * dp[i + 1][2] + dp[i + 1][3]) % MOD
        else:
            dp[i][0] = (dp[i + 1][0] + int(S[i] == "A") * dp[i + 1][1]) % MOD
            dp[i][1] = (dp[i + 1][1] + int(S[i] == "B") * dp[i + 1][2]) % MOD
            dp[i][2] = (dp[i + 1][2] + int(S[i] == "C") * dp[i + 1][3]) % MOD
    print(dp[0][0])


# time complexity: O(|S|)
def focus_on_B():
    # cuml = {"A": [], 
    #         "C": [],
    #         "?": []}
    # current_nums = {"A": 0,
    #                 "C": 0,
    #                 "?": 0}
    # for char in S:
    #     if char in cuml.keys():
    #         current_nums[char] += 1
    #     for key in cuml.keys():
    #         cuml[key].append(current_nums[key])

    cuml = [[0] * 3 for _ in range(len(S))]
    num_A = num_C = num_q = 0
    for i, char in enumerate(S):
        if char == "A":
            num_A += 1
        elif char == "C":
            num_C += 1
        elif char == "?":
            num_q += 1
        cuml[i][0] = num_A
        cuml[i][1] = num_C
        cuml[i][2] = num_q

    num_combinations = 0
    for i in range(1, len(S) - 1):
        if S[i] in {"B", "?"}:
            A_L = cuml[i-1][0]
            Q_L = cuml[i-1][2]
            C_R = cuml[-1][1] - cuml[i][1]
            Q_R = cuml[-1][2] - cuml[i][2]
            left_pow = 3**Q_L
            right_pow = 3**Q_R
            num_combinations += (A_L * left_pow + Q_L * left_pow//3) * (C_R * right_pow + Q_R * right_pow//3)
            if num_combinations >= MOD:
                num_combinations %= MOD
    print(num_combinations)

focus_on_B()


### FIXED CODE ###

S = input()

MOD = 10**9 + 7
dp = [[0] * 4 for _ in range(len(S) + 1)]
dp[len(S)][3] = 1
for i in range(len(S))[::-1]:
    dp[i][3] = 3 * dp[i + 1][3] if S[i] == "?" else dp[i + 1][3]
    dp[i][3] %= MOD
    if S[i] == "?":
        dp[i][0] = (3 * dp[i + 1][0] + dp[i + 1][1]) % MOD
        dp[i][1] = (3 * dp[i + 1][1] + dp[i + 1][2]) % MOD
        dp[i][2] = (3 * dp[i + 1][2] + dp[i + 1][3]) % MOD
    else:
        dp[i][0] = (dp[i + 1][0] + int(S[i] == "A") * dp[i + 1][1]) % MOD
        dp[i][1] = (dp[i + 1][1] + int(S[i] == "B") * dp[i + 1][2]) % MOD
        dp[i][2] = (dp[i + 1][2] + int(S[i] == "C") * dp[i + 1][3]) % MOD
print(dp[0][0])
### BUGGY CODE ###

from fractions import gcd
N,M = map(int,input().split())
S,T = [input() for i in range(2)]
for i in range(N):
  for j in range(M):
    if i*M == j*N and S[i] != T[j]:
        print(-1)
        exit()
    elif i == N-1 and j == M-1:
      print(int(N*M/gcd(N,M)))
      
      

### FIXED CODE ###

import fractions
N,M = map(int,input().split())
S = input(); T = input()
gcd = fractions.gcd(N,M)
N_prime = N //gcd; M_prime = M // gcd
for i in range(0,N,N_prime):
    for j in range(0,M,M_prime):
        if i * M_prime - j * N_prime == 0 and S[i] != T[j]:
            print(-1)
            exit()
print(N*M // gcd)
### BUGGY CODE ###

def prime(p):
    memo = set()
    for i in range(2,(int(p**0.5)+1)):
        while p%i==0:
            p //= i
            memo.add(i)
    if p != 1:
        memo.add(p)
    return memo

from math import gcd

N = int(input())

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

tmp_gcd = A[0]

for i in range(1,N):
    tmp_gcd = gcd(tmp_gcd, A[i])

if 1 < tmp_gcd:
    print('not coprime')
    exit()

servive_prime = set()
for a in A:
    now_prime = prime(a)
    tmp_prime = servive_prime.union(now_prime)
    if len(tmp_prime) < len(servive_prime) + len(now_prime):
        print('setwise coprime')
        exit()
    servive_prime = tmp_prime
print('pairwise coprime')
    

### FIXED CODE ###

def prime(p):
    memo = set()
    for i in range(2,(int(p**0.5)+1)):
        while p%i==0:
            p //= i
            memo.add(i)
    if p != 1:
        memo.add(p)
    return memo

from math import gcd

N = int(input())

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

tmp_gcd = A[0]

for i in range(1,N):
    tmp_gcd = gcd(tmp_gcd, A[i])

if 1 < tmp_gcd:
    print('not coprime')
    exit()

servive_prime = set()
for a in A:
    now_prime = prime(a)
    ls,ln = len(servive_prime), len(now_prime)
    servive_prime.update(now_prime)
    if len(servive_prime) < ls + ln:
        print('setwise coprime')
        exit()
print('pairwise coprime')
### BUGGY CODE ###

import sys

args = sys.argv

# print(args)

def f(arg_list):
    even_arg_list = []
    for i in arg_list:
        if i % 2 == 0:
            even_arg_list.append(i/2)
        else:
            return False
    return even_arg_list


counter = 0
_list = map(lambda x:int(x),args[1:])
while True:
    _list = f(_list)
    if _list == False:
        print(counter)
        sys.exit()
    counter+=1
    # print(_list)
    

### FIXED CODE ###

import sys

N = int(input())
Ai = map(lambda x:int(x),input().split(" "))
 
def f(arg_list):
    even_arg_list = []
    for i in arg_list:
        if i % 2 == 0:
            even_arg_list.append(i/2)
        else:
            return False
    return even_arg_list


counter = 0
while True:
    Ai = f(Ai)
    if Ai == False:
        print(counter)
        sys.exit()
    counter+=1
    # print(Ai)
### BUGGY CODE ###

from collections import Counter
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def f(c1, c2, c3):
    if dp[c1][c2][c3] is not None:
        return dp[c1][c2][c3]

    res = (n \
           + (f(c1 - 1, c2, c3) * c1 if c1 else 0) \
           + (f(c1 + 1, c2 - 1, c3) * c2 if c2 else 0) \
           + (f(c1, c2 + 1, c3 - 1) * c3 if c3 else 0)) \
          / (c1 + c2 + c3)
    dp[c1][c2][c3] = res
    return res


n = int(input())
a = tuple(map(int, input().split()))

dp = tuple(
    tuple(
        [None] * (n + 1) for _ in range(n + 1)
    ) for _ in range(n + 1))
dp[0][0][0] = 0
# dp[x][y][z]:=1,2,3個の皿がx,y,z残っているときの期待値

c = Counter(a)
c1 = c[1]
c2 = c[2]
c3 = c[3]

print(f(c1, c2, c3))

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p


### FIXED CODE ###

def main():
    from collections import Counter

    n = int(input())
    a = tuple(int(x) for x in input().split())

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    x1 = 310 ** 2
    x2 = 310

    dp = [0.0] * (310 ** 3)
    dp[0] = 0.0
    # dp[x * x1 + y * x2 + z]:=1,2,3個の皿がx,y,z残っているときの期待値

    for r3 in range(c3 + 1):
        d3 = c3 - r3
        for r2 in range(c2 + d3 + 1):
            for r1 in range(c1 + d3 + c2 - r2 + 1):
                ind = r1 * x1 + r2 * x2 + r3
                if ind != 0:
                    dp[ind] = (n \
                               + (dp[ind - x1] * r1 if r1 > 0 else 0) \
                               + (dp[ind + x1 - x2] * r2 if r2 > 0 else 0) \
                               + (dp[ind + x2 - 1] * r3 if r3 > 0 else 0)) \
                              / (r1 + r2 + r3)

    print(dp[c1 * x1 + c2 * x2 + c3])


if __name__ == '__main__':
    main()

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p

# if mainの追加
# 初期値None->-1.0にした
# checked配列を辞めた
# チェック済みかどうかの判定を-1.0と一致するかの比較にした

# カウントはCounterを使う方が速い
# 1次元にした
# resの加算を複数回に分けると
# 三項演算子より遅くなる
# 再帰関数を辞めた
### BUGGY CODE ###

from _collections import deque
N=int(input())
numbers=[]
for _ in range(N-1):
    u,v,w=input().split()
    numbers.append([int(u)-1,int(v)-1,int(w)])
inf=pow(10,9)
route=[[inf for _ in range(N)] for _ in range(N)]
for a in numbers:
    route[a[0]][a[1]]=a[2]
    route[a[1]][a[0]]=a[2]
visited_point=[inf for _ in range(N)]
visited_point[0]=0
stack=deque([0])
while len(stack)>0:
    n=stack.pop()
    number=0
    for z in route[n]:
        if z==inf:
            number+=1
            continue
        if visited_point[number]==inf:
            visited_point[number]=visited_point[n]+z
            stack.appendleft(number)
        number+=1
for a in visited_point:
    if a%2==0:
        print(0)
    else:
        print(1)
        

### FIXED CODE ###

from collections import deque
N=int(input())
numbers=[[] for _ in range(N)]
for _ in range(N-1):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    numbers[u].append((v,w%2))
    numbers[v].append((u,w%2))
inf=pow(10,9)
visited_point=[inf for _ in range(N)]
visited_point[0]=0
stack=deque([0])
while len(stack)>0:
    n=stack.pop()
    for v,w in numbers[n]:
        if visited_point[v]==inf:
            stack.appendleft(v)
            if w%2==0:
                visited_point[v]=visited_point[n]
            else:
                visited_point[v]=visited_point[n]^1
for a in visited_point:
    print(a)
### BUGGY CODE ###

from collections import deque
n = int(input())

q = deque()
for _ in range(n):
  num = int(input())
  if num in q:
    q.remove(num)
  else:
    q.append(num)
    
print(len(q))

### FIXED CODE ###

import collections

n = int(input())
a = [int(input()) for _ in range(n)]
c = dict(collections.Counter(a))

ans = 0

for _,val in c.items():
  if val % 2 == 1:
    ans += 1
    
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

H, N = map(int, input().split())
magic = [_ for _ in range(N)]

for k in range(N):
  magic[k] = list(map(int, input().split()))
  magic[k].append(magic[k][0]/magic[k][1])

magic.sort(key = lambda x: x[2], reverse=True)
ans = [0 for _ in range(H+1)]
visited = [0]
anskouho = []

def solve(start, power, point, maryoku):
  if start >= H:
    anskouho.append(point)
    visited.sort(reverse=True)
    return 0
  elif ans[start] != 0:
    visited.sort(reverse=True)
    return 0
  else:
    visited.append(start)
    ans[start] = point
    solve(start+power, power, point+maryoku, maryoku)

for k in range(N):
  for item in visited:
    solve(item+magic[k][0], magic[k][0], ans[item] + magic[k][1], magic[k][1])

print(min(anskouho))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

H, N = map(int, input().split())
magic = [_ for _ in range(N)]

for k in range(N):
  magic[k] = list(map(int, input().split()))
  magic[k].append(magic[k][0]/magic[k][1])

magic.sort(key = lambda x: x[2], reverse=True)
ans = [0 for _ in range(H+1)]
visited = [0]
anskouho = [float('inf')]

def solve(start, power, point, maryoku):
  if start == H:
    print(min(point, min(anskouho)))
    exit()
  elif start > H:
    anskouho.append(point)
    visited.sort(reverse=True)
    return 0
  elif ans[start] != 0:
    visited.sort(reverse=True)
    return 0
  else:
    visited.append(start)
    ans[start] = point
    solve(start+power, power, point+maryoku, maryoku)

for k in range(N):
  for item in visited:
    solve(item+magic[k][0], magic[k][0], ans[item] + magic[k][1], magic[k][1])

print(min(anskouho))
### BUGGY CODE ###

def main():
    t = input()
    if t == "1":
        print(1)
        exit(0)
    li = [int(v) for v in input().split(' ')]
    s_li = sorted(li)
    count = 0
    for v in range(s_li[0] - 1, s_li[-1] + 1):
        t_c = 0
        for vv in s_li:
            if v == vv or v - 1 == vv or v + 1 == vv:
                t_c += 1
            if vv + 2 > v:
                continue
        if t_c > count:
            count = t_c

    print(count)



if __name__ == '__main__':
    main()

### FIXED CODE ###

n = int(input())
cnt = [0] * 100002
a = list(map(int, input().split()))
for v in a:
    cnt[v] += 1
    cnt[v+1] += 1
    cnt[v+2] += 1
    
print(max(cnt))
### BUGGY CODE ###

def main():
    n = int(input())
    p = [i for i in range(1, n+1)]

    ans = sum([p[i] % (p[i]+1) for i in range(n-1)])
    # for i in range(n-1):
    #     ans += p[i] % (p[i]+1)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())

    ans = n * (n-1)//2
    print(ans)


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

import sys
input = sys.stdin.readline
h,w=map(int,input().split())
a=[]
for i in range(h):
    a.append(list(map(int,input().split())))
b=[]
for i in range(h):
    b.append(list(map(int,input().split())))
dp=[[set([]) for i in range(w)] for j in range(h)]
dp[0][0].add(a[0][0]-b[0][0])
dp[0][0].add(b[0][0]-a[0][0])
for i in range(h):
    for j in range(w):
        if i==j==0:
            continue
        if i==0:
            for k in dp[i][j-1]:
                #if k+a[i][j]-b[i][j]>=0:
                dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                #if -k+a[i][j]-b[i][j]>=0:
                  #  dp[i][j].add(-k+a[i][j]-b[i][j])
                #if k+b
                dp[i][j].add(abs(k+b[i][j]-a[i][j]))
        elif j==0:
            for k in dp[i-1][j]:
                dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                dp[i][j].add(abs(k+b[i][j]-a[i][j]))
        else:
            for k in (dp[i][j-1]|dp[i-1][j]):
                dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                dp[i][j].add(abs(k+b[i][j]-a[i][j]))             
#dp[h-1][w-1]
ans=10**10
for i in dp[h-1][w-1]:
    ans=min(ans,abs(i))
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W=map(int,input().split())
a = [[] for _ in range(H)]
for i in range(H):
    a[i] = list(map(int, input().split()))
b = [[] for _ in range(H)]
for i in range(H):
    b[i] = list(map(int, input().split()))

for i in range(H):
    for j in range(W):
        a[i][j] =abs(a[i][j]-b[i][j])

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(a[0][0])
for i in range(1,H):
    t = a[i][0]
    tmp = set()
    for k in dp[i-1][0]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[i][0] = tmp
for j in range(1,W):
    t = a[0][j]
    tmp = set()
    for k in dp[0][j-1]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[0][j] = tmp
for i in range(1,H):
    for j in range(1,W):
        t = a[i][j]
        tmp = set()
        for k in (dp[i-1][j] | dp[i][j-1]):
            tmp.add(k+t)
            tmp.add(abs(k-t))
        dp[i][j] = tmp
        dp[i-1][j-1] = set()

ls = list(dp[H-1][W-1])
print(min(ls))
### BUGGY CODE ###

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


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


k = n * m // gcd(n, m)


for i in range(k, n * m + 1, k):
    ss = {a * (i // n) for a in range(n)}
    tt = {a * (i // m) for a in range(m)}
    st = ss & tt
    flag = True
    for c in st:
        if S[c * n // i] != T[c * m // i]:
            flag = False
            break
    if flag:
        print(i)
        exit()
print(-1)

### FIXED CODE ###

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


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


k = n * m // gcd(n, m)


for i in range(k, n * m + 1, k):
    g = i * i // n // m // gcd(i // n, i // m)
    flag = True
    for c in range(0, i, g):
        if S[c * n // i] != T[c * m // i]:
            flag = False
            break
    if flag:
        print(i)
        exit()
print(-1)
### BUGGY CODE ###

import math
import functools
import copy

N=int(input())
a=list(map(int,input().split()))
b=copy.copy(a)
ans=list()

for i in range(len(a)):
  del b[i]
  gcd=functools.reduce(math.gcd,b)
  ans.append(gcd)
  b.insert(i,a[i])

print(max(ans))

### FIXED CODE ###

import math
from itertools import accumulate

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

fromleft = list(accumulate(a, math.gcd))
fromright = list(accumulate(a[::-1], math.gcd))[::-1]

gcd = []

gcd.append(fromright[1])
for i in range(1, n-1):
    gcd.append(math.gcd(fromleft[i-1], fromright[i+1]))
gcd.append(fromleft[n-2])

print(max(gcd))
### BUGGY CODE ###

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

# N: 買う品物の個数
# M: 持っている割引券の数
N, M = list(map(int, input().split()))

# X 円の品物を買う際に Y 枚の割引券を使った場合、その品物を (X/2^Y) 円(小数点以下切り捨て)で買うことができます。
# 最小で何円あれば全ての品物を買うことができるのか?

# アイディア
# 単に高い商品から順に割引券を使えればよい...
# ただ、割引券は 10^5 枚ありえるようなので、
# 普通に並び替えて最大なものに割引券を適用する...というのを繰り返しても、
# タイムアウトになるだろう。
# うーん...
#
# 単に大きい順にソートして割引券を適用して、
# そのあとは挿入ソートを使って順繰りに割引券を適用するというのはどうだろうか
# やってみようか
A = list(map(int, input().split()))
A.sort(reverse=True)
# print(A)

for i in range(M):
    # 1. 先頭を半額にする
    # 2. 挿入ソートする (最初は手抜きでタイムアウトするか調べる)
    A[0] = A[0] / 2
    A.sort(reverse=True)

print(sum([int(x) for x in A]))


### FIXED CODE ###

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

# N: 買う品物の個数
# M: 持っている割引券の数
N, M = list(map(int, input().split()))

# X 円の品物を買う際に Y 枚の割引券を使った場合、その品物を (X/2^Y) 円(小数点以下切り捨て)で買うことができます。
# 最小で何円あれば全ての品物を買うことができるのか?

# アイディア
# 単に高い商品から順に割引券を使えればよい...
# プライオリティキューを使って最大のものから順次割引していけばよさそう
# Python のプライオリティキューは最小値しか取れないため、すべての値を (* -1) して考える (出力時にまた (* -1) して戻す)
A = [-x for x in map(int, input().split())]
heapq.heapify(A)


for i in range(M):
    # M 回割引券を適用する
    minimal = heapq.heappop(A)
    heapq.heappush(A, minimal / 2)

print(sum([int(x) for x in A]) * -1)
### BUGGY CODE ###

n, m = map(int, input().split())
p = list(map(int, input().split()))
g = []
for i in range(m):
    g.append(list(map(int, input().split())))
l = [[] for i in range(n+1)]
for pi in g:  
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
x =  [0]*n
for i in range(n):
  x[p[i]-1] = i+1
ans = 0
#Union find
y = [-1] * n
for i in range(0,n):
  if y[i] == -1:
    y[i] = i
  c = l[i+1]
  while len(c) > 0:
    z = c.pop()
    y[z-1] = y[i]
    for j in range(len(l[z])):
      if y[l[z][j]-1] == -1:
        c.append(l[z][j])
    
for i in range(n):
  c = x[i]
  if y[c-1] == y[i]:
    ans +=1
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
p = list(map(int, input().split()))
g = []
for i in range(m):
    g.append(list(map(int, input().split())))
l = [[] for i in range(n+1)]
for pi in g:  
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
x =  [0]*n
for i in range(n):
  x[p[i]-1] = i+1
ans = 0
#Union find
y = [-1] * n
for i in range(0,n):
  if y[i] == -1:
    y[i] = i
  c = l[i+1]
  while len(c) > 0:
    z = c.pop()
    y[z-1] = y[i]
    for j in range(len(l[z])):
      if y[l[z][j]-1] == -1:
        c.append(l[z][j])
    l[z] =[]
    
for i in range(n):
  c = x[i]
  if y[c-1] == y[i]:
    ans +=1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat May 25 21:57:15 2019

@author: Yamazaki Kenichi
"""
import bisect

Q = int(input())
Q2 = [input() for i in range(Q)]

ans = []
A = []
B = 0
C = 0
counta = 0
d, prea, b = map(int,Q2[0].split()) 
for q in Q2:
    if q[0] == '1':
#        input
        d, a, b = map(int,q.split()) 
        bisect.insort_left(A,a)
#        if A[(len(A)-1)//2] > a:
#            C = abs(prea - a)
#        else:
#            C = abs(A[(len(A)-1)//2] - a)
        C = abs(A[(len(A)-1)//2] - a) if counta % 2 == 0 else abs(prea - a)
        B += (b + C)
#        C = abs(prea - a)
        prea = A[(len(A)-1)//2]
        counta += 1
    else:
#        output
        tmp = A[(len(A)-1)//2]
        ans.append([tmp,B])
for c in ans:
    print(' '.join(map(str,c)))


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue May 28 22:22:21 2019

@author: Yamazaki Kenichi
"""
import heapq

Q = int(input())
Q2 = [input() for i in range(Q)]

ans = []
Al,Ar = [-(-(10**9+1))],[10**9+1]
B = 0
flg = False
for q in Q2:
    if q[0] == '1':
#        input
        d, a, b = map(int,q.split())
        if not flg:
            heapq.heappush(Al,-a)
            B += b
            flg = True
            continue
        
#        C = abs(a - (-Al[0]))
        if len(Al) == len(Ar):
            if a < Ar[0]:
#                C = abs(a - (-Al[0]))
                heapq.heappush(Al,-a)
#                C = abs(a - (-Al[0]))
#            elif a < Ar[0]:
#                heapq.heappush(Al,-(heapq.heappop(Ar)))
#                heapq.heappush(Ar,a)
                C = abs(a - (-Al[0]))
            else:
                heapq.heappush(Ar,a)
                heapq.heappush(Al,-(heapq.heappop(Ar)))
                C = abs(a - (-Al[0]))
        else:
            if a < Ar[0]:
                C = abs(a - (-Al[0]))
                heapq.heappush(Al,-a)
                heapq.heappush(Ar,-(heapq.heappop(Al)))
#                C = abs(a - (-Al[0]))
#            elif a < A[]
            else:
                C = abs(a - (-Al[0]))
                heapq.heappush(Ar,a)
#                C = abs(a - (-Al[0]))
        B += (b + C)
#        print(Al,Ar,a,B,b)
    else:
#        output
        ans.append([(-Al[0]),B])
        
for c in ans:
    print(' '.join(map(str,c)))
### BUGGY CODE ###

import collections
n = str(input())
ans,div = 0,[]
for i in range(0,len(n)):
        k = int(n[i:len(n)])
        div.append(k % 2019)
div.append(0)
c = collections.Counter(div)
values, counts = zip(*c.most_common())
for i in range(0,len(counts)):
    ans += counts[i] *(counts[i]-1) /2
print(int(ans))

### FIXED CODE ###

import collections
n = str(input())
ans,m,div = 0,0,[]
for i,j in enumerate(reversed(n)):
    m=(m+int(j)*pow(10,i,2019))%2019
    div.append(m)
div.append(0)
c = collections.Counter(div)
values, counts = zip(*c.most_common())
for i in range(0,len(counts)):
    ans += counts[i] *(counts[i]-1) /2
print(int(ans))
### 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

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
# def LIST(): return list(map(str, input().split()))
# def LIST(): return list(input())

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, W = MAP()
L = [LIST() for _ in range(N)]

dp = [[0] * (W+1) for i in range(N+1)]
# for w, v in L:
for i in range(1, W+1):
    for j in range(1, N+1):
        w = L[j-1][0]
        v = L[j-1][1]
        if i - w >= 0: 
            dp[j][i] = max(dp[j-1][i-w] + v, dp[j][i])
        dp[j][i] = max(dp[j][i], dp[j-1][i])

print(dp[N][W])




### 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

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
# def LIST(): return list(map(str, input().split()))
# def LIST(): return list(input())

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, W = MAP()
L = [LIST() for _ in range(N)]

dp = [[0] * (W+1) for i in range(N+1)]
# for w, v in L:
for i in range(1, W+1):
    for j in range(1, N+1):
        w = L[j-1][0]
        v = L[j-1][1]
        if i - w >= 0: 
            dp[j][i] = max(dp[j-1][i-w] + v, dp[j][i])
        dp[j][i] = max(dp[j][i], dp[j-1][i])

print(dp[N][W])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np


# なんこか入力
l,r = map(int, input().split())

answer = 9999
for j in range(l,r+1):
    for i in range(l,j):
        a = i % 2019
        b = j % 2019
        answer = min(answer,(a*b)%2019)

print(answer)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np


# なんこか入力
l,r = map(int, input().split())

if r-l >= 2019:
    r = l+2019
else:
    r = l + (r-l) % 2019

answer = 9999
for j in range(l,r+1):
    for i in range(l,j):
        a = i % 2019
        b = j % 2019
        answer = min(answer,(a*b)%2019)

print(answer)