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

from itertools import product, chain
from collections import deque


def solver1(a, b, c, k):
    apb_sorted = sorted([a + b for a, b in product(a, b)])[-k:]
    ans_list = sorted(
        list(chain.from_iterable([[_c + ab for ab in apb_sorted] for _c in c[:k]]))
    )
    it = reversed(ans_list)
    for _ in range(k):
        print(next(it))


def solver2(a, b, c, k):
    d = deque()
    n = len(a)
    m = min(k, n)
    for p in range(m):
        for q in range(m):
            for r in range(m):
                if (p + 1) * (q + 1) * (r + 1) > k:
                    continue
                d.append(a[-p - 1] + b[-q - 1] + c[-r - 1])
    it = reversed(sorted(d))
    for _ in range(k):
        print(next(it))


if __name__ == "__main__":
    x, y, z, k = list(map(int, input().split(" ")))
    a = sorted(list(map(int, input().split(" "))))
    b = sorted(list(map(int, input().split(" "))))
    c = sorted(list(map(int, input().split(" "))))
    solver2(a, b, c, k)


### FIXED CODE ###

from itertools import product, chain

x, y, z, k = list(map(int, input().split(" ")))
a = sorted(list(map(int, input().split(" "))))
b = sorted(list(map(int, input().split(" "))))
c = sorted(list(map(int, input().split(" "))))

apb_sorted = sorted([a + b for a, b in product(a, b)])[-k:]
ans_list = sorted(
    list(chain.from_iterable([[_c + ab for ab in apb_sorted] for _c in c[:k]]))
)
it = reversed(ans_list)
for _ in range(k):
    print(next(it))
### BUGGY CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

def root(uft, x):
    if uft[x] == x: return x
    uft[x] = root(uft, uft[x])
    return uft[x]

def union(uft, x, y):
    x = root(uft, x)
    y = root(uft, y)
    if x == y:
        return
    uft[x] = y

def answer():
    n, m, k = map(int, input().split())
    friend = defaultdict(set)
    block = defaultdict(set)
    group = defaultdict(set)
    uft = [i for i in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        union(uft, a, b)
        friend[a].add(b)
        friend[b].add(a)
    for j in range(k):
        c, d = map(int, input().split())
        block[c].add(d)
        block[d].add(c)
    for i in range(1, n+1):
        root(uft, i)
    for i in range(1, n+1):
        group[root(uft, i)].add(i)
    return ' '.join(str(len(group[uft[i]]-block[i])-len(friend[i])-1) for i in range(1, n+1))

print(answer())



### FIXED CODE ###

from collections import defaultdict, Counter
import sys

def root(uft, x):
    if uft[x] == x: return x
    uft[x] = root(uft, uft[x])
    return uft[x]

def union(uft, rank, x, y):
    x = root(uft, x)
    y = root(uft, y)
    if x == y:
        return

    if rank[x] >= rank[y]:
        uft[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
    else:
        uft[x] = y

def same(uft, x, y):
    return root(uft, x) == root(uft, y)

def answer():
    n, m, k = map(int, input().split())
    friend = defaultdict(int)
    block = defaultdict(int)
    group = defaultdict(set)
    uft = [i for i in range(n+1)]
    rank = [0] * (n+1)
    for i in range(m):
        a, b = map(int, input().split())
        union(uft, rank, a, b)
        friend[a] += 1
        friend[b] += 1
    for j in range(k):
        c, d = map(int, input().split())
        if not same(uft, c, d):
            continue
        block[c] += 1
        block[d] += 1
    for i in range(1, n+1):
        root(uft, i)
    c = Counter(uft)
    return [c[uft[i]]-block[i]-friend[i]-1 for i in range(1, n+1)]

print(*answer())
### BUGGY CODE ###

from collections import deque

n, x, y = map(int, input().split())

graph = [[i-1,i+1] for i in range(n+1)]
graph[1]=[2]
graph[n]=[n-1]
graph[0]=[0]

graph[x].append(y)
graph[y].append(x)

def bfs(start,graph2):
    dist = [-1] * (n+1)
    dist[0] = 0
    dist[start] = 0

    d = deque()
    d.append(start)
    while d:
        v = d.popleft()
        for i in graph2[v]:
            if dist[i] != -1:
                continue
            dist[i] = dist[v] + 1
            d.append(i)
        
    dist = dist[start+1:]
    return dist

ans = [0]*n
for j in range(1,n):
    dist = bfs(j,graph)
    for k in range(1,n):
        ans[k] += dist.count(k)
    
for x in range(1,n):
    print(ans[x])



### FIXED CODE ###

from collections import deque

n, x, y = map(int, input().split())

graph = [[i-1,i+1] for i in range(n+1)]
graph[1]=[2]
graph[n]=[n-1]
graph[0]=[0]

graph[x].append(y)
graph[y].append(x)

def bfs(start,graph2):
    dist = [-1] * (n+1)
    dist[0] = 0
    dist[start] = 0

    d = deque()
    d.append(start)
    while d:
        v = d.popleft()
        for i in graph2[v]:
            if dist[i] != -1:
                continue
            dist[i] = dist[v] + 1
            d.append(i)
        
    dist = dist[start+1:]
    return dist

ans=[0 for _ in range(n-1)]
for i in range(1,n+1):
    for j in bfs(i,graph):
        ans[j-1] +=1
 
for i in ans:
    print(i)
### BUGGY CODE ###

# coding: utf-8

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

## S中で、'AC'であるインデックスを求める
index = [0] * N
i = 0
while i < len(S)-1:
    if S[i]=='A' and S[i+1]=='C':
        index[i] = 1
        i += 2
    else:
        i += 1

#print('\n')
#print(index)

for i in range(Q):
    l, r = map(int, input().split())
    l = l-1
    r = r-1
    print( sum(index[l : r]) )


### FIXED CODE ###

# coding: utf-8

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

num = [0] * (N+1)

for i in range(N):
    #if S[i]=='A' and S[i+1]=='C':
    if S[i:i+2] =='AC':
        num[i + 1] = num[i] + 1
    else:
        num[i + 1] = num[i]

        

for i in range(Q):
    l, r = map(int, input().split())
    print( num[r-1] - num[l-1] )
### BUGGY CODE ###

import math,itertools,fractions,heapq,bisect,sys,copy,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j,0))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      while len(q)>0:
        y,x,c=q.popleft()
        visited[y][x]=c

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if 0<=ny<h and 0<=nx<w:
            if field[ny][nx]=='#':
              continue
            if visited[ny][nx]!=-1:
              continue
            q.append((ny,nx,c+1))
      ans=max(ans,c)
  return ans

# main()
print(main())


### FIXED CODE ###

import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      visited[i][j]=0
      _ans=0
      while q:
        y,x=q.popleft()

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if not 0<=ny<h:
            continue
          if not 0<=nx<w:
            continue
          if field[ny][nx]=='#':
            continue
          if visited[ny][nx]!=-1:
            continue
          _ans=visited[y][x]+1
          visited[ny][nx]=_ans
          q.append((ny,nx))
      ans=max(ans,_ans)
  return ans

# main()
print(main())
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int, input().split()))
sum = 0
last = 0
for num in range(K):
  last += A[num]
for i in range(1,N-K+1):
  for j in range(K):
    sum += A[i+j]
  if last < sum:
    print("Yes")
  else:
    print("No")
  last = sum
  sum = 0

### FIXED CODE ###

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

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

s = raw_input().strip()
n = len(s)
x, y = map(int, raw_input().strip().split())

st = 0
while st < n and s[st] == "F":
    st += 1

x -= st

X, Y = range(2)

x_blocks = []
y_blocks = []
curr = 0
cdi = X

for i in xrange(st, n):
    ch = s[i]
    if ch == "F":
        curr += 1
    else:
        if curr != 0:
            if cdi == X:
                x_blocks.append(curr)
            else:
                y_blocks.append(curr)
        curr = 0
        cdi = (cdi + 1) % 2
if curr != 0:
    if cdi == X:
        x_blocks.append(curr)
    else:
        y_blocks.append(curr)

x, y = abs(x), abs(y)
lxb, lyb = len(x_blocks), len(y_blocks)
sxb, syb = sum(x_blocks), sum(y_blocks)
x_blocks = sorted(x_blocks)
y_blocks = sorted(y_blocks)

if sum(x_blocks) < x or sxb % 2 != x % 2 or sum(y_blocks) < y or syb % 2 != y % 2:
    print "No"
    exit()

tx = (x + sxb) / 2
stack = [([0] * lxb, 0, -1)]
xgood = False

while stack:
    curr, val, top = stack.pop()
    if val == tx:
        xgood = True
        break
    for i in xrange(top + 1, lxb):
        if val + x_blocks[i] > tx:
            break
        nxt = curr[::]
        nxt[i] = 1
        stack.append((nxt, val + x_blocks[i], i))
    if xgood:
        break

if not xgood:
    print "No"
    exit()

ty = (y + syb) / 2
stack = [([0] * lyb, 0, -1)]
ygood = False

while stack:
    curr, val, top = stack.pop()
    if val == ty:
        ygood = True
        break
    for i in xrange(top + 1, lyb):
        if val + y_blocks[i] > ty:
            break
        nxt = curr[::]
        nxt[i] = 1
        stack.append((nxt, val + y_blocks[i], i))
    if ygood:
        break

if not ygood:
    print "No"
else:
    print "Yes"


### FIXED CODE ###

from collections import defaultdict as dd

s = raw_input().strip()
n = len(s)
x, y = map(int, raw_input().strip().split())

stx = 0
while stx < n and s[stx] == "F":
    stx += 1

sty = 0

X, Y = range(2)

x_blocks = []
y_blocks = []
curr = 0
cdi = X

for i in xrange(stx, n):
    ch = s[i]
    if ch == "F":
        curr += 1
    else:
        if curr != 0:
            if cdi == X:
                x_blocks.append(curr)
            else:
                y_blocks.append(curr)
        curr = 0
        cdi = (cdi + 1) % 2
if curr != 0:
    if cdi == X:
        x_blocks.append(curr)
    else:
        y_blocks.append(curr)

curr = dd(int)
curr[stx] = 1

for xb in x_blocks:
    nxt = dd(int)

    for key in curr.iterkeys():
        nxt[key + xb] += 1
        nxt[key - xb] += 1

    curr = nxt

if x not in curr:
    print "No"
    exit()

curr = dd(int)
curr[sty] = 1

for yb in y_blocks:
    nxt = dd(int)

    for key in curr.iterkeys():
        nxt[key + yb] += 1
        nxt[key - yb] += 1

    curr = nxt

if y not in curr:
    print "No"
else:
    print "Yes"
### BUGGY CODE ###

import numpy as np

        
n = int(input())

a = np.zeros(n,dtype=int)
b = np.zeros(n,dtype=int)

for i in range(n):
    a[i],b[i] = map(float, input().split())

#listをsortする
if n==2:
    a0 = [a[0]]
    b0 = [b[0]]
    if a[1]>=a[0]:
        a0.append(a[1])
    else:
        a0.insert(0,a[1])
    if b[1]>=a[0]:
        b0.append(b[1])
    else:
        b0.insert(0,b[1])
else:
    a0 = [a[0]]
    b0 = [b[0]]
    if a[1]>=a[0]:
        a0.append(a[1])
    else:
        a0.insert(0,a[1])
    if b[1]>=a[0]:
        b0.append(b[1])
    else:
        b0.insert(0,b[1])    
    for i in range(2,n):
        if a[i]>=a0[len(a0)-1]:
            a0.append(a[i])
        elif a[i]<=a0[0]:
            a0.insert(0,a[i])
        else:
            l = 0
            for j in range(len(a0)-1):
                if a0[j]<=a[i] and a[i]<=a0[j+1] and l==0:
                    a0.insert(j+1,a[i])
                    l = 1
        if b[i]>=b0[len(b0)-1]:
            b0.append(b[i])
        elif b[i]<=b0[0]:
            b0.insert(0,b[i])
        else:
            m = 0
            for j in range(len(b0)-1):
                if b0[j]<=b[i] and b[i]<=b0[j+1] and m==0:
                    b0.insert(j+1,b[i])
                    m = 1

                    
if n%2 == 1:
    a0cen = a0[(n-1)//2]
    b0cen = b0[(n-1)//2]
    nn = b0cen - a0cen + 1
else:
    a0cen1 = a0[(n-2)//2]+a0[n//2]
    b0cen1 = b0[(n-2)//2]+b0[n//2]
    nn = int(b0cen1 -a0cen1 +1)

print(nn)           
            

### FIXED CODE ###

import numpy as np

        
n = int(input())

a = np.zeros(n,dtype=int)
b = np.zeros(n,dtype=int)

for i in range(n):
    a[i],b[i] = map(float, input().split())

#listをsortする
a.sort()
b.sort()
                    
if n%2 == 1:
    a0cen = a[(n-1)//2]
    b0cen = b[(n-1)//2]
    nn = b0cen - a0cen + 1
else:
    a0cen1 = a[(n-2)//2]+a[n//2]
    b0cen1 = b[(n-2)//2]+b[n//2]
    nn = int(b0cen1 -a0cen1 +1)

print(nn)
### BUGGY CODE ###

S = input()
p = 10 ** 9 + 7
DP = [[0 for j in range(4)] for i in range(len(S) + 1)]
DP[len(S)][3] = 1
for i in range(len(S) - 1, -1, -1):
  for j in range(3, -1, -1):
    if j == 3:
      DP[i][j] = DP[i + 1][3] * (3 if S[i] == '?' else 1)
    else:
      DP[i][j] += DP[i + 1][j + 1] * (1 if S[i] == chr(65 + j) or S[i] == '?' else 0)
      DP[i][j] += DP[i + 1][j] * (3 if S[i] == '?' else 1)
print(DP[0][0] % p)

### FIXED CODE ###

S = input()
p = 10 ** 9 + 7
DP = [0, 0, 0, 1]
dp = [0] * 4
for i in range(len(S) - 1, -1, -1):
  for j in range(3, -1, -1):
    if j == 3:
      dp[j] = DP[3] * (3 if S[i] == '?' else 1) % p
    elif S[i] == '?':
      dp[j] = (3 * DP[j] + DP[j + 1]) % p
    elif S[i] == chr(65 + j):
      dp[j] = (DP[j] + DP[j + 1]) % p
    else:
      dp[j] = DP[j]
  DP = [x for x in dp]
print(DP[0] % p)
### BUGGY CODE ###

N = int(input().strip())
x = [[] for x in range(N)]
for i in range(N-1):
     u, v, w = list(map(int, input().split()))
     x[u-1].append([v-1, w])
     x[v-1].append([u-1,w])



ret = {}
done = []

queue = [0]

for i in range(N):
    curr = queue.pop()
    if curr == 0:
        ret[0] = 0

    for neigh in x[curr]:
        if neigh[1] % 2 == 0:
            ret[neigh[0]] = ret[curr]
        else:
            ret[neigh[0]] = 0 if ret[curr] == 1 else 1

        if neigh[0] not in done:
            queue.append(neigh[0])
    done.append(curr)


for i in range(N):
    print(ret[i])


### FIXED CODE ###

N = int(input().strip())
x = [[] for x in range(N)]
for i in range(N-1):
     u, v, w = list(map(int, input().split()))
     x[u-1].append([v-1, w%2])
     x[v-1].append([u-1,w%2])



ret = {}
done = [0 for x in range(N)]

queue = [0]

for i in range(N):
    curr = queue.pop()
    if curr == 0:
        ret[0] = 0

    for neigh in x[curr]:
        if done[neigh[0]] == 1:
            continue
        if neigh[1] % 2 == 0:
            ret[neigh[0]] = ret[curr]
        else:
            ret[neigh[0]] = 0 if ret[curr] == 1 else 1

        queue.append(neigh[0])
    done[curr] = 1


for i in range(N):
    print(ret[i])
### BUGGY CODE ###

s = input()
mod = 10 ** 9 + 7
#dp[k] -> 13で割ったあまりがkのパターン数
dp = [0] * 13
dp[0] = 1
mul = 1

for c in s[::-1]:
  #次の状態
  nextDP = [0] * 13
  if c == "?":
    for k in range(10):
      for j in range(13):
        nextDP[(k * mul + j)%13] += dp[j]
        nextDP[(k * mul + j)%13] %= mod
      
  else:
    k = int(c)
    for j in range(13):
        nextDP[(k * mul + j)%13] += dp[j]
        nextDP[(k * mul + j)%13] %= mod

  mul *= 10
  mul %= 13
  dp = nextDP

print(dp[5])


### FIXED CODE ###

s = input()
mod = 10 ** 9 + 7
#dp[k] -> 13で割ったあまりがkのパターン数
dp = [0] * 13
dp[0] = 1
mul = 1

for c in s[::-1]:
  #次の状態
  nextDP = [0] * 13
  if c == "?":
    for k in range(10):
      for j in range(13):
        nextDP[(k * mul + j)%13] += dp[j]
        nextDP[(k * mul + j)%13] %= mod
      
  else:
    k = int(c)
    for j in range(13):
        nextDP[(k * mul + j)%13] += dp[j]
        nextDP[(k * mul + j)%13] %= mod

  mul *= 10
  mul %= 13
  dp = nextDP

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

h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(map(int, input().split())))
for i in range(h):
    l = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = grid[i][j] - l[j]

unba = []

# 0行目
l = [{grid[0][0], -grid[0][0]}]
for i in range(1, w):
    l1 = {j + grid[0][i] for j in l[i-1]}
    l2 = {j - grid[0][i] for j in l[i-1]}
    l.append(l1 | l2)
unba.append(l)

# 1~h-1行目
for i in range(1, h):

    # i行0列
    l1 = {j + grid[i][0] for j in unba[i-1][0]}
    l2 = {j - grid[i][0] for j in unba[i-1][0]}
    l = [l1 | l2]

    # i行j列
    for j in range(1, w):
        l1 = {k + grid[i][j] for k in l[j-1]}
        l2 = {k - grid[i][j] for k in l[j-1]}
        l3 = {k + grid[i][j] for k in unba[i-1][j]}
        l4 = {k - grid[i][j] for k in unba[i-1][j]}
        l.append(l1 | l2 | l3 | l4)
    unba.append(l)

ans = abs(unba[h-1][w-1].pop())
for i in unba[h-1][w-1]:
    if abs(i) < ans:
        ans = abs(i)
print(ans)

### FIXED CODE ###

def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

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

    m = (h + w) * 80

    if m == 0:
        print(0)
        exit()

    dp = [[False] * m for _ in range(w)]
    dp[0][g[0][0]] = True
    for j in range(1, w):
        for k in range(m):
            if dp[j-1][k]:
                dp[j][abs(k - g[0][j])] = True
                dp[j][k + g[0][j]] = True
    
    for i in range(1, h):
        new_dp = [[False] * m for _ in range(w)]
        for k in range(m):
            if dp[0][k]:
                new_dp[0][abs(k - g[i][0])] = True
                new_dp[0][k + g[i][0]] = True
        
        for j in range(1, w):
            for k in range(m):
                if new_dp[j-1][k] or dp[j][k]:
                    new_dp[j][abs(k - g[i][j])] = True
                    new_dp[j][k + g[i][j]] = True
        dp = new_dp

    for j in range(m):
        if dp[w-1][j]:
            print(j)
            break

main()
### BUGGY CODE ###

n=int(input())
s = input().split(' ')
ans=1
for i in s:
    ans=ans*int(i)
if(ans>1000000000000000000):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n=int(input())
s = input().split(' ')
ans=1
for i in s:
    if int(i) == 0:
        print(0)
        exit()
for i in s:
    ans=ans*int(i)
    if(ans>1000000000000000000):
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

import numpy as np
from numba import jit
     
MOD = 998244353
N, K = list(map(int, input().split()))
     
dp = np.zeros(N+1, dtype=np.int64)
mv = np.zeros(N+1, dtype=np.int64)
for i in range(K):
    l, r = list(map(int, input().split()))
    for j in range(l, r+1):
        mv[j] = 1

@jit
def shift_and_add(dp, mv, i):
    for i in range(1, N+1):
        dp += np.concatenate((np.zeros(i+1, dtype=np.int64), mv[1:N-i+1]*dp[i]))
        dp %= MOD
            
dp[1] = 1
shift_and_add(dp, mv, i)
     
print(dp[N])


### FIXED CODE ###

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

a = [0] * (N+1)
f = [0] * (N+1)
mv = list()
for i in range(K):
    mv.append(list(map(int, input().split())))

def solve(N, a, f):
    for i in range(1, N+1):
        f[i] = (f[i-1] + a[i]) % MOD
        for j in range(len(mv)):
            l, r = mv[j]
            if i+l < N+1: a[i+l] = (a[i+l] + f[i]) % MOD
            if i+r+1 < N+1: a[i+r+1] = (a[i+r+1] - f[i]) % MOD

a[1] = 1
mv.sort()
solve(N, a, f)

print(a[N])
### BUGGY CODE ###

lim=10**9+7
H=int(input())
A=[int(i) for i in input().split()]

#M=[[0]*H for _ in range(H)]
#K=[[0]*H for _ in range(H)]
for N in range(0,H+1):
    sum_=0
    sum2=0
    for i in range(N):
        for j in range(i+1,N):
            #M[i][j]=A[i]^A[j]
            #K[i][j]=A[i]+A[j]
            sum_ = (sum_+(A[i]^A[j])) % lim
            #sum2 = (sum2+(A[i]+A[j])) 
print(sum_)
#print(sum2)
#print(sum2-sum_)
#print("###")

### FIXED CODE ###

lim = 10**9+7
n=int(input())
A=[int(i) for i in input().split()]
binary = [bin(i)[2:].zfill(60)[::-1] for i in A]

ans=0
for i in range(60):
    l = [s[i] for s in binary]
    #print(i,l.count("0") * l.count("1"))
    ans = (ans+ ((l.count("0") * l.count("1"))% lim * 2**i )% lim)% lim
print(ans % lim)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N, W = map(int, input().split())
    item = []
    for _ in range(N):
        w, v = map(int, input().split())
        item.append((w, v))

    dp = [0] * (W + 1)
    for w, v in item:
        for i in range(W + 1)[::-1]:
            if i - w >= 0:
                tmp = dp[i - w] + v
                if tmp > dp[i]:
                    dp[i] = tmp

    print(max(dp))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def main():
    input = sys.stdin.readline

    N, W = map(int, input().split())
    dp = [0] * (W + 1)

    WV = (map(int, input().split()) for _ in range(N))

    for w, v in WV:
        for j in range(W, w - 1, -1):
            tmp = dp[j - w] + v
            if tmp > dp[j]:
                dp[j] = tmp

    print(dp[-1])


main()
### BUGGY CODE ###

N,K=map(int,input().split())
z=[tuple(map(int,input().split()))for _ in range(N)]
x=[i for i,_ in z]
y=[j for _,j in z]
x.sort()
y.sort()
a=10**20
for i in range(N):
    for j in range(i+1,N):
        for k in range(N):
            for l in range(k+1,N):
                l,r,d,u=x[i],x[j],y[k],y[l]
                if sum([l<=v<=r and d<=w<=u for v,w in z])>=K:
                    a=min(a,(r-l)*(u-d))
print(a)

### FIXED CODE ###

n,k=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(n)]
z.sort()
a=10**20
for i in range(n):
    for j in range(i+1,n):
        x=z[j][0]-z[i][0]
        l=sorted(t[1]for t in z[i:j+1])
        for u,v in zip(l,l[k-1:]):
            a=min(a,x*(v-u))
print(a)
### BUGGY CODE ###

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

results = set()

for i in range(1000):
    # 対象となる3桁の数字を用意
    filled_num = str(i).zfill(3)
    target = list(filled_num)
    count = 0
    index = 0
    for j in range(3):
        for k in range(index, len(S), 1):
            if S[k] == target[j]:
                count += 1
                index = k + 1
                break
    if count == 3:
        # print(filled_num)
        results.add(filled_num)

print(len(results))


### FIXED CODE ###

def test(original: list, nums: str, index: int,
         remain_count: int, results: set, results_1, results_2):
    # 3桁抽出したら終了
    if len(nums) == 1:
        if nums in results_1:
            return
        results_1.add(nums)
    if len(nums) == 2:
        if nums in results_2:
            return
        results_2.add(nums)
    if len(nums) == 3:
        # print("".join(array))
        results.add(nums)
        return
    # 最終桁に到達したら終了
    if index == len(original):
        return
    for i in range(index, len(original), 1):
        test(
            original,
            nums + original[i],
            i + 1,
            remain_count,
            results,
            results_1,
            results_2)

    # この桁を抽出対象としないパターン
    # test(original, array[:], index + 1, remain_count - 1, results)


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

results = set()
results_1 = set()
results_2 = set()

# N個の要素
# N-3個を削除
# 3個の組み合わせが何通りあるか？
test(S, "", 0, N - 3, results, results_1, results_2)

print(len(results))