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

n,w=map(int,input().split())
dp=[[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
	a,b=map(int,input().split())
	for j in range(w):
		if j+1-a>=0:
			dp[i+1][j+1]=max(dp[i][j+1],dp[i][j+1-a]+b)
		else:
			dp[i+1][j+1]=dp[i][j+1]
print(dp[-1][-1])


### FIXED CODE ###

n,w=map(int,input().split())
dp=[[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
	a,b=map(int,input().split())
	for j in range(w):
		if j+1-a>=0:
			dp[i+1][j+1]=max(dp[i][j+1],dp[i][j+1-a]+b)
		else:
			dp[i+1][j+1]=dp[i][j+1]
print(dp[-1][-1])
### BUGGY CODE ###

from collections import deque
from collections import Counter
import numpy as np
n,x,y = map(int,input().split())
x,y = x-1 ,y-1
g = [[float('inf')]*n for _ in range(n)]
for i in range(n):
    que = deque([(i, 0)])
    while que:
        node, cost = que.popleft()
        if g[i][node]!=float('inf'):
            continue
        else:
            g[i][node] = cost
            if node>0:
                que.append((node-1, cost+1))
            if node<n-1:
                que.append((node+1, cost+1))
            if node==x:
                que.append((y, cost+1))
            if node==y:
                que.append((x, cost+1))
array = np.array(g).flatten().tolist()
cnt = Counter(array)
for i in range(1, n):
    print(cnt[i] // 2)

### FIXED CODE ###

from collections import deque
n,x,y = map(int,input().split())
x,y = x-1 ,y-1
g = [[float('inf')]*n for _ in range(n)]
for i in range(n):
    que = deque([(i, 0)])
    while que:
        node, cost = que.popleft()
        if g[i][node]!=float('inf'):
            continue
        else:
            g[i][node] = cost
            if node>0:
                que.append((node-1, cost+1))
            if node<n-1:
                que.append((node+1, cost+1))
            if node==x:
                que.append((y, cost+1))
            if node==y:
                que.append((x, cost+1))
cnt = [0]*n
for i in range(n):
    for j in range(i+1, n):
        cnt[g[i][j]] += 1
for c in cnt[1:]:
    print(c)
### BUGGY CODE ###

mod = 10**9+7
n = int(input())
s = input()
d = {}
for i in s:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
result = 0
for i in range(1, 2**len(d)):
    c = 1
    num = i
    for n, j in d.items():
        if num%2==1:
            c = (c*j)%mod
        num >>= 1
    result = (result+c)%mod

print(result%mod)

### FIXED CODE ###

mod = 10**9+7
n = int(input())
s = input()
d = {}
for i in s:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
result = 1
for i, j in d.items():
    result = (result*(j+1))%mod

print((result-1)%mod)
### BUGGY CODE ###

from collections import defaultdict
import sys

input = sys.stdin.readline

def main():
    H, W, M = map(int, input().split())
    d = defaultdict(int)
    e = defaultdict(int)
    X = []
    for _ in range(M):
        h, w = map(int, input().split())
        d[h] += 1
        e[w] += 1
        X.append((h,w))
    
    a = max(d.values())
    b = max(e.values())
    cand_d = []
    cand_e = []
    for i, j in d.items():
        if j == a:
            cand_d.append(i)

    for i, j in e.items():
        if j == b:
            cand_e.append(i)

    for i in cand_d:
        for j in cand_e:
            if not (i,j) in X:
                ans = a + b
                print(ans)
                exit()

    print(a + b - 1)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import defaultdict
import sys

input = sys.stdin.readline

def main():
    H, W, M = map(int, input().split())
    d = defaultdict(int)
    e = defaultdict(int)
    x = defaultdict(set)
    y = defaultdict(set)
    X = []
    for _ in range(M):
        h, w = map(int, input().split())
        d[h] += 1
        e[w] += 1
        x[h].add(w)
        y[w].add(h)
        
    a = max(d.values())
    b = max(e.values())
    cand_d = set()
    cand_e = set()
    for i, j in d.items():
        if j == a:
            cand_d.add(i)

    for i, j in e.items():
        if j == b:
            cand_e.add(i)

    for i in cand_d:
        if (cand_e - x[i]) != set():
            ans = a + b
            print(ans)
            exit()

    for i in cand_e:
        if (cand_d - y[i]) != set():
            ans = a + b
            print(ans)
            exit()

    print(a + b - 1)


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

l,r = map(int,input().split())
c = 4*10**18
for i in range(l,r):
    for j in range(i+1,r+1):
        d = (i*j)%2019
        if d < c:
            c = d
print(c)

### FIXED CODE ###

l,r = map(int,input().split())
r = min(r,l+2019)
c = [4*10**18]
for i in range(l,r):
    for j in range(i+1,r+1):
        c.append((i*j)%2019)
print(min(c))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)
a.append(0)
cost = [abs(x - y) for x, y in zip(a[:-1], a[1:])]
for i in range(n):
    print(sum(cost) - cost[i] - cost[i + 1] + abs(a[i] - a[i + 2]))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)
a.append(0)
c = [abs(x - y) for x, y in zip(a[:-1], a[1:])]
c_sum = sum(c)
for i in range(n):
    print(c_sum - c[i] - c[i + 1] + abs(a[i] - a[i + 2]))
### BUGGY CODE ###

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

W, V = [0], [0]
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
# print('W', W)
# print('V', V)
# dp[i][sum_w] := i-1 番目までの品物から重さが sum_w を超えないように選んだときの、価値の総和の最大値
# dp[i + 1][sum_w], dp[i][sum_w - w[i]] + v[i]

dp = [[0] * (_W + 2) for _ in range(N + 3)]
for i in range(1, N + 1):
    w, v = W[i], V[i]
    for sum_w in range(_W + 1):
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
        if sum_w - w < 0:
            continue
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - w] + v)

import numpy as np
# print('dp')
print(np.array(dp).max())


### FIXED CODE ###

import numpy as np

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

W, V = [0], [0]
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
# dp[i][sum_w] := i-1 番目までの品物から重さが sum_w を超えないように選んだときの、価値の総和の最大値
# dp[i + 1][sum_w], dp[i][sum_w - w[i]] + v[i]

dp = np.array([0] * (_W + 1))
for i in range(1, N + 1):
    w, v = W[i], V[i]
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
    # print(dp)

# print('dp')
print(dp.max())
### BUGGY CODE ###

import math
import itertools
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


n = int(input())
a = list(map(int,input().split()))
a.sort()
#b = list(itertools.combinations(a,2))
ans = [0,(0,0)]
#print(b)
for i in range(n-1):
    tmpans = combinations_count(a[-1],a[i])
    if tmpans >= ans[0]:
        ans = [tmpans,(a[-1],a[i])]
        
print(ans[1][0],ans[1][1])

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
dis = [abs(a[-1]/2 - a[i]) for i in range(n-1)]
r = a[dis.index(min(dis))]
print(a[-1],r)
### BUGGY CODE ###

N = int(input())
x_list = list(map(int, input().split()))

result = 1
for x in x_list:
  result *= x
if result >1e18:
  print(-1)
else:
  print(result)

### FIXED CODE ###

import math
 
N = int(input())
x_list = list(map(int, input().split()))
 
result = 1
if 0 in x_list:
  print(0)
  exit()
for x in x_list:
  result *= x
  if result > 1e18:
    print(-1)
    exit()
print(result)
### BUGGY CODE ###

n = int(input())
p = list(map(lambda x: int(x), input().split()))

count = 0
for i in range(n):
  a = p[i]
  alist = p[:i+1]
  alist.sort()
  if alist[0] == a:
    count += 1
print(count)

### FIXED CODE ###

n = int(input())
p = list(map(lambda x: int(x), input().split()))
 
count = 0
maxs = p[0]
for i in range(n):
  if maxs >= p[i]:
    maxs = p[i]
    count += 1
print(count)
### BUGGY CODE ###

# coding:utf-8
import numpy
n = int(input())
a = list(map(int, input().split()))
ans = 0

for i in range(n - 1):
    cum = numpy.cumsum(a[i + 1:])
    ans += a[i] * cum[-1]

print(ans % (10**9 + 7))


### FIXED CODE ###

# coding:utf-8
import itertools
n = int(input())
a = list(map(int, input().split()))
cum = [0] + list(itertools.accumulate(a))
# print(cum)
ans = 0
mod = 10**9 + 7

for i in range(n):
    ans += a[i] * cum[i]
    # print(a[i], cum[i])

print(ans % mod)
### BUGGY CODE ###

import numpy as np

N, Q = (int(x) for x in input().split())

dic = {}

for i in range(N-1) :
    #a, b = (int(x) for x in input().split())
    a, b = map(int,input().split())
    dic[b] = a

SUM = np.zeros(N, dtype=np.int)

for i in range(Q) :
    #p, x = (int(x) for x in input().split())
    p, x = map(int,input().split())
    SUM[p-1] = SUM[p-1] + x

for i in range(N-1) :
    SUM[i+1] += SUM[dic.get(i+2)-1]

print(' '.join(map(str, SUM)))

### FIXED CODE ###


import numpy as np

N, Q = (int(x) for x in input().split())

dic = {}

for i in range(N-1) :
    #a, b = (int(x) for x in input().split())
    a, b = map(int,input().split())
    dic[b] = a

#SUM = np.zeros(N, dtype=np.int)
SUM = [0]*N

for i in range(Q) :
    #p, x = (int(x) for x in input().split())
    p, x = map(int,input().split())
    SUM[p-1] = SUM[p-1] + x

for i in range(N-1) :
    SUM[i+1] += SUM[dic.get(i+2)-1]

print(' '.join(map(str, SUM)))
### BUGGY CODE ###

import itertools
n, x = map(int, input().split())
d = [tuple(map(int, input().split())) for _ in range(x)]
c = [tuple(map(int, input().split())) for _ in range(n)]

ans = float("inf")
for v in itertools.permutations(list(range(1, x+1)), 3):
    tmp2 = 0
    for i in range(3):
        tmp1 = 0
        j = 0
        k = i
        while k <= 2*n-2:
            for l in range(n):
                if -l + k < 0 or -l + k >= n:
                    continue
                tmp1 += d[c[-l+k][l]-1][v[i]-1]
            j += 1
            k = 3*j+i
        tmp2 += tmp1
    ans = min(ans, tmp2)
print(ans)


### FIXED CODE ###

import itertools
N, C = map(int, input().split())
D = [tuple(map(int, input().split())) for _ in range(C)]
c = [tuple(map(lambda x: x-1, map(int, input().split()))) for _ in range(N)]

grid = [[0] * C for _ in range(3)]
for i, j in itertools.product(range(N), repeat=2):
    grid[(i+j)%3][c[i][j]] += 1

ans = float("inf")
for color_after in itertools.permutations(range(C), 3):
    s = sum([sum([grid[g][color_before]*D[color_before][color_after[g]] for color_before in range(C)]) for g in range(3)])
    ans = min(ans, s)

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

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def cc(v, pp):
	if v == pp[-1]:
		return False, -1
	
	for p in pp:
		if v % p == 0:
			return False, 0
		if v < 2*p:
			return True, 0
	return True, 0
			

def main():
	n = int(input())
	#b , c = tin()
	#s = input()
	al = lin()
	al.sort()
	pp=[al[0]]
	n_same=0
	n_same_set=set()
	for v in al[1:]:
		tf, vv = cc(v, pp)
		if tf:
			pp.append(v)
		if vv == -1 and pp[-1] not in n_same_set:
			n_same_set.add(pp[-1])
			n_same += vv
	print(len(pp) + n_same)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	n = int(input())
	#b , c = tin()
	al = lin()
	al.sort()
	
	unique_al = list(set(al))
	unique_al.sort()
	
	al_counter = collections.Counter(al)
	ok=[v for v in al_counter.keys() if al_counter[v] == 1]
	d = {v:i for i,v in enumerate(ok)}
	max_v = 10**6+1
	for check in unique_al:
		for v in range(2*check, max_v, check):
			if v in d:
				ok[d[v]]=0
				
	return sum([v > 0 for v in ok ])
		
	
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

from collections import Counter
import itertools as it
MOD = 10 ** 9 + 7
n = int(input())
s = input()

b = Counter(s)
c = list(b)

ans = 0
for i in range(1,len(b)+1):
    d = list(it.combinations(c,i))
    for j in d:
        a = 1
        for k in j:
            a = a*b[k]
            
        ans = (ans+a) %MOD
            
print(ans)

### FIXED CODE ###

from collections import Counter
import itertools as it
MOD = 10 ** 9 + 7
n = int(input())
s = input()

b = Counter(s)
c = list(b)

ans = 1
for i in b:
    ans = ans * (b[i]+1) % MOD
    
print((ans + MOD - 1) % MOD)
### BUGGY CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
K = int(input())
youso = 0

for i in range(K):
    i = i + 1
    for k in range(K):
        k = k + 1
        for j in range(K):
            j = j + 1
            youso += gcd(i, k, j)
            j = j + 1
        k = k + 1
    i = i + 1
            
    

print(youso)



### FIXED CODE ###

K = int(input())
ans = 0
from math import gcd
for i in range(1,K+1):
    for k in range(1,K+1):
        for j in range(1,K+1):
            ans += gcd(gcd(i, k),j)
            
print(ans)
### BUGGY CODE ###

import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

S = input()

div_num = 1000000007
arr = np.arange(13, dtype = int)
# dp = [[0 for _ in range(13)] for _ in range(len(S))]
dp = np.zeros([len(S), 13], dtype = int)

if S[-1] == "?":
    for ii in range(10): dp[0, ii] = 1
else:
    dp[0, int(S[-1])] = 1

for ii in range(1, len(S)):
    ind = -ii-1
    if S[ind] == '?':
        for n in range(10):
            res = (((10 ** ii) * n) % 13 + arr) % 13
            dp[ii, res] += dp[ii - 1, arr]
            dp[ii, res] %= div_num
    else:
        res = (((10 ** ii) * int(S[ind])) % 13 + arr) % 13
        dp[ii, res] += dp[ii - 1, arr]
        dp[ii, res] %= div_num

print (dp[-1, 5])


### FIXED CODE ###

import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

# S = [int(x) if x!="?" else -1 for x in input()]

# print (S)

# div_num = 1000000007
# arr = np.arange(13, dtype = np.uint64)
# # dp = np.zeros([2, 13], dtype = np.uint64)

# div13_list = [1]
# for ii in range(1, len(S)):
#     n = div13_list[-1] * 10 % 13
#     if n in div13_list:
#         break
#     else:
#         div13_list.append(n)
# div13_mat = np.array([div13_list] * 10, dtype = int)
# div13_mat = (div13_mat * np.arange(10)[:, None] % 13).T

# if S[-1] == -1:
#     dp[0, :10] = 1
# else:
#     dp[0, S[-1]] = 1

# for ii in range(1, len(S)):
#     # ind = -ii-1
#     # tmp = div13_mat[ii%6]
#     # if S[ind] == -1:
#     #     for n in range(10):
#     #         res = np.roll(arr, -tmp[n])
#     #         # dp[1, res] += dp[0, arr]
#     # else:
#     #     res = np.roll(arr, -tmp[S[ind]])
#     #     # dp[1, res] += dp[0, arr]
#     dp[0] = dp[1] % div_num
#     dp[1] = 0


# print (dp[0, 5])

#
# 大きい方の桁からやってく方法
#

MOD = 1000000007;

S = [int(x) if x!="?" else -1 for x in input()]
n = len(S)

# r[i]
# 現在考えてる一つ前の桁数で、余りが i になる整数の個数
r = [0] * 13

# まず一つ目の値が１の位とする
s = S[0]
if (s != -1):
    r[s] = 1
else:
    for i in range(10): r[i] = 1

# 桁を進めながら個数をカウント
for i in range(1, n):
    # dp[j]
    # 現在考えている桁(i)を除く、余りが j となる整数の個数
    dp = [0] * 26

    # 桁が一つ上がるので、一つ前の余りが 10 倍になる
    for j in range(13):
        dp[j*10%13] += r[j] % MOD

    # アクセスを高速にするため２倍の長さとる (dp[i] == dp[i + 13])
    dp[13:26] = dp[0:13]

    r = [0]*13

    s = S[i]
    if (s == -1):
        w = sum(dp[4:14])
        for j in range(13):
            r[j] += w
            w += dp[j + 1]-dp[j + 4]
    else:
        for j in range(13):
            r[j] += dp[13-s+j]
print (r[5]%MOD)
### BUGGY CODE ###

N, W = map(int, input().split())
INF = -10 ** 12

# 重さW以下の時の価値の最大値
dp = [[0 for _ in range(W + 1)] for _ in range(N)]

for i in range(0, N):
    w, v = map(int, input().split())
    for j in range(W + 1):
        if j - w >= 0:
            dp[i][j] = max(dp[i - 1][j - w] + v, dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]

print(dp[N - 1][W])

### FIXED CODE ###

import numpy as np

N, W = map(int, input().split())
INF = -10 ** 12

# 重さW以下の時の価値の最大値
dp = np.zeros((N, W + 1), dtype=np.int64)

for i in range(0, N):
    w, v = map(int, input().split())
    dp[i][:w] = dp[i-1][:w]
    dp[i][w:] = np.maximum(dp[i-1][w:], dp[i-1][:-w] + v)

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

H,W = list(map(int,input().split()))
M = []
for i in range(H):
    M.append(list(input()))

Bs = []
for i in range(H):
    for j in range(W):
        if M[i][j]=="#":
            Bs.append([i,j])

from collections import deque
memo = [[float("inf")] * W for i in range(H)]
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
que = deque([])
que.append(Bs)
for Bi,Bj in Bs:
    memo[Bi][Bj] = 0

while que:
    ps = que.popleft()
    next = []
    for p in ps:
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if (0<=nx<W)and(0<=ny<H)and(memo[ny][nx]==float("inf")):
                next.append((ny, nx))
                memo[ny][nx] = memo[p[0]][p[1]] + 1
    if len(next)>0:
        que.append(next)

out = 0
for i in range(H):
    for j in range(W):
        if memo[i][j]>out:
            out = memo[i][j]
print(out)

### FIXED CODE ###

H,W = list(map(int,input().split()))
M = []
for i in range(H):
    M.append(list(input()))

Bs = []
for i in range(H):
    for j in range(W):
        if M[i][j]=="#":
            Bs.append([i,j])

from collections import deque
memo = [[2000] * W for i in range(H)]
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
que = deque([])
que.append(Bs)
for Bi,Bj in Bs:
    memo[Bi][Bj] = 0

out = 0
while que:
    ps = que.popleft()
    next = []
    for p in ps:
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if (0<=nx<W)and(0<=ny<H)and(memo[ny][nx]==2000):
                next.append((ny, nx))
                memo[ny][nx] = memo[p[0]][p[1]] + 1
                if memo[ny][nx]>out:
                    out=memo[ny][nx]
    if len(next)>0:
        que.append(next)

print(out)
### BUGGY CODE ###

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

d = [[a[i][0]-a[i][1],a[i][0]+a[i][1]] for i in range(n)]

d = sorted(d, key = lambda x: x[1])
#print(d)

b = [-100000000000000000]
c = [0]


for i in range(n):
    for j in range(len(b)):
        if d[i][0] >= b[j]:
            b.append(d[i][1])
            c.append(c[j]+1)
    
#print(b)
#print(c)

print(max(c))
        
    


### FIXED CODE ###

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

d = [[a[i][0]-a[i][1],a[i][0]+a[i][1]] for i in range(n)]

d = sorted(d, key = lambda x: x[1])
#print(d)

b = [-100000000000000000]
c = [0]


for i in range(n):
    for j in range(len(b)):
        if d[i][0] >= b[j]:
            b = [d[i][1]]
            c = [c[j] + 1]
            break

    
    #print(b)
    #print(c)

print(max(c))
### BUGGY CODE ###

N=int(input())
A=[int(x) for x in input().split()]
bit= [bin(x ^ y) for x in A for y in A]
B=sorted(set(bit))[1:]
AA=[]
for a in A:
  AA.append(bin(a))
if all(a in B for a in AA):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

import collections
N=int(input())
A=[int(x) for x in input().split()]
AA=sorted(A)
c=collections.Counter(A)
third=N//3
answer="No"

#文字が全部0
if all(a==0 for a in A):
  answer="Yes"

#0aa0aaという並びに出来る
#0がN/3個,aが2N/3個で数字は二種類
elif len(c)==2 and N%3==0:
  if all(a==0 for a in AA[:third]):
    answer="Yes"
     
#abc,abc...,abcという並びに出来る
#aがN/3個,bがN/3個,cがN/3個で数字は三種類
elif len(c)==3 and N%3==0:
  if A.count(AA[0])==third and \
  A.count(AA[third])==third and \
  A.count(AA[2*third])==third:
    if bin(AA[0]^AA[third])==bin(AA[2*third]) and \
    bin(AA[third]^AA[2*third])==bin(AA[0]) and \
    bin(AA[2*third]^AA[0])==bin(AA[third]):
      answer="Yes"
    
print(answer)
### BUGGY CODE ###

S=input()
src=[0]*2019
ans=0
pre=0
for s in range(len(S)):
  a=(int(S[-(s+1)])*(10**s)+pre)%2019
  src[a]+=1
  pre+=int(S[-(s+1)])*(10**s)
  ans+=src[a]-1
print(ans+src[0])

### FIXED CODE ###

S=input()
N=len(S)

a=0
t=1
d=[0]*2019
d[0]=1
for i in range(N):
  a+=int(S[N-1-i])*t
  a%=2019
  t*=10
  t%=2019
  d[a]+=1

ans=0
for n in d:
  ans += n*(n-1)//2
print(ans)
### BUGGY CODE ###


import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True

def main():
    N, M = LMIIS()
    dp = [0] * (M+1)

    DV = [[0] for _ in range(M+1)]

    for _ in range(N):
        A,B = LMIIS()
        if A > M:
            continue
        DV[A].append(B)

    for i in range(1,M+1):
        DV[i].sort(reverse=True)
        DV[i] = DV[i][:M-i+1]
    ans = 0
    tmpL = []
    for l in DV:
        tmpL += l
        tmpL.sort(reverse=True)
        ans += tmpL.pop(0)
    print(ans)
        
        



    pass
if __name__ == '__main__':
    main()


### FIXED CODE ###


import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True

def main():
    N, M = LMIIS()
    dp = [0] * (M+1)

    DV = [[0] for _ in range(M+1)]

    for _ in range(N):
        A,B = LMIIS()
        if A > M:
            continue
        DV[A].append(B)


    from heapq import heappush, heappop
    ans = 0
    h = []
    for l in DV:
        for item in l:
            heappush(h,-item)
        ans -= heappop(h)
    print(ans)
        
        



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

N = int(input().rstrip())
a = input().split()
H = []
count = 0
countmax = 0

for i in range(len(a)):
  H.append(int(a[i]))
H.append(10000000000)
  
for j in range(len(a)):
  for k in range(j, len(a)):
    if(H[k] >= H[k+1]):
      count += 1
    else:
      break
  if(countmax < count):
    countmax = count
  count = 0

print(countmax)

### FIXED CODE ###

N = int(input().rstrip())
a = input().split()
H = []
count = []

for i in range(len(a)):
  H.append(int(a[i]))
H.append(10000000000)

temp = 0
for j in range(len(a)):
  if(H[j] >= H[j+1]):
    temp += 1
  else:
    count.append(temp)
    temp = 0

print(max(count))
### BUGGY CODE ###

def main():
    R,B,G,N = list(map(int,input().split(' ')))
    cnt = 0
    for i in range(N//R+1):
        for j in range(N//G+1):
            if R*i+G*j > N:
              break
            if (N-(R*i+G*j))//B == (N-(R*i+G*j))/B and (N-(R*i+G*j))/B >=0:
                cnt +=1
    print(cnt)

if __name__ =='__main__':
    main()

### FIXED CODE ###

def main():
    R,B,G,N = list(map(int,input().split(' ')))
    cnt = 0
    for r in range(N//R+1):
        for g in range(N//G+1):
            if R*r+G*g > N:
                break
            if (N-(R*r+G*g))%B ==0:

                cnt +=1
    print(cnt)
if __name__ =='__main__':
    main()
### BUGGY CODE ###

a,b,c,d=map(int,input().split())
count=0
for i in range(a,b+1):
    if i%c !=0:
        if i%d !=0:
            count+=1
print(count)

### FIXED CODE ###

import fractions
a,b,c,d=map(int,input().split())
cd=int(c*d/(fractions.gcd(c,d)))
#print(cd)
c1=b//c
c2=(a-1)//c
c3=c1-c2
d1=b//d
d2=(a-1)//d
d3=d1-d2
cd1=b//(cd)
cd2=(a-1)//(cd)
cd3=cd1-cd2
print((b-a+1)-(c3+d3-cd3))
#print(str(c3)+" "+str(d3)+" "+str(cd3))