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

N, M, K = map(int, input().split())
block_list = [[i] for i in range(N)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def set(self):
      [self.find(self.parents[i]) for i in range(self.n)]
      
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

uf = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  uf.union(a-1, b-1)
  block_list[a-1].append(b-1)
  block_list[b-1].append(a-1)
for i in range(K):
  a, b = map(int, input().split())
  block_list[a-1].append(b-1)
  block_list[b-1].append(a-1)
uf.set()
ans = []
for i in range(N):
  ans.append(len([j for j in uf.members(i) if not j in block_list[i]]))
print(*ans)

### FIXED CODE ###

N, M, K = map(int, input().split())
block_list = [[i] for i in range(N)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def same(self, x, y):
        return self.find(x) == self.find(y)

uf = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  uf.union(a-1, b-1)
  block_list[a-1].append(b-1)
  block_list[b-1].append(a-1)
for i in range(K):
  a, b = map(int, input().split())
  if uf.same(a-1, b-1):
    block_list[a-1].append(b-1)
    block_list[b-1].append(a-1)
ans = []
for i in range(N):
  ans.append(uf.size(i) - len(block_list[i]))
print(*ans)
### BUGGY CODE ###

import heapq
def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    BC = []
    for i in range(M):
        tmp = list(map(int, input().split()))
        BC.append(tmp)
    BC.sort(reverse=True, key=lambda x: x[1])
        
    heapq.heapify(A)
    for i in range(M):
        for j in range(BC[i][0]):
            if BC[i][1] < A[0]:
                break
            heapq.heapreplace(A, BC[i][1])
    
    print(sum(A))


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    N, M = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    operate = []
    for _ in range(M):
        b, c = map(int,input().split())
        operate.append([b,c])
    operate.sort(reverse=True, key=lambda x:x[1])    

    rewrite = [0] * N
    idx = 0
    for b,c in operate:
        for i in range(b):
            rewrite[idx] = c
            idx += 1
            if idx == N:
                break
        if idx == N:
            break
    
    ans = 0
    for i in range(N):
        ans += max(A[i],rewrite[i])
    
    print(ans)

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

N, H = list(map(int, input().split()))
a = []
b = []
for i in range(N):
    temp0, temp1 = list(map(int, input().split()))
    a.append(temp0)
    b.append(temp1)

b_temp = []
for i in b:
    if max(a) <= i:
        b_temp.append(i)
b = b_temp
if H <= sum(b):
    b.sort()
    for i in range(len(b)):
        H -= b[-1 - i]
        if H <= 0:
            result = i + 1
            break
else:
    if len(b) != 0:
        H -= sum(b)
    dev = int(H / max(a))
    if H % max(a) != 0:
        dev += 1
    result = len(b) + dev

print(result)


### FIXED CODE ###

import numpy as np

N, H = list(map(int, input().split()))
a = []
b = []
for i in range(N):
    temp0, temp1 = list(map(int, input().split()))
    a.append(temp0)
    b.append(temp1)

b = np.array(b)
b = b[max(a) < b]
# b_temp = []
# for i in b:
#     if max(a) <= i:
#         b_temp.append(i)
# b = b_temp
if H <= sum(b):
    # b.sort()
    b = np.sort(b)
    for i in range(len(b)):
        H -= b[-1 - i]
        if H <= 0:
            result = i + 1
            break
else:
    if len(b) != 0:
        H -= sum(b)
    dev = int(H / max(a))
    if H % max(a) != 0:
        dev += 1
    result = len(b) + dev

print(result)
### BUGGY CODE ###

n=int(input())
s=[]
for i in range(n):
    s.append(list(str(input())))
    s[i].sort()

x=0
for l in range(n):
    for m in range(l+1,n):
        if s[l]==s[m]:
            x+=1
print(x)


### FIXED CODE ###

n=int(input())
s=[''.join(sorted(input())) for i in range(n)]
ans=0
dict={}
for i in s:
    if i in dict:
        ans+=dict[i]
        dict[i]+=1
    else:
        dict[i]=1
print(ans)
### BUGGY CODE ###

K = int(input())

#偶数、5の倍数はありえない
if(K % 2 == 0):
    print(-1)
    exit()

if(K % 5 == 0):
    print(-1)
    exit()

ans = 1
tmp = 7
for i in range(1*10**6):
    if tmp % K == 0:
        print(ans)
        exit()
    
    ans += 1
    tmp += (7 * 10**(ans-1)) % K
#    print(ans, tmp)

print(-1)


### FIXED CODE ###

K = int(input())

#偶数、5の倍数はありえない
if(K % 2 == 0):
    print(-1)
    exit()

if(K % 5 == 0):
    print(-1)
    exit()

ans = 1
tmp = 7
for i in range(1*10**6):
    if tmp % K == 0:
        print(ans)
        exit()
    
    hoge = tmp % K
    ans += 1
    tmp = hoge * 10 + 7
#    print(ans, tmp)

print(-1)
### BUGGY CODE ###

import math
import sys
import queue
import copy
import bisect#2分探索

def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())
def inputl():
    return list(map(int, input().split()))
def printl(li):
    print(*li, sep="\n")
def argsort(s):
    return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

N = inputi()
#N, K = inputl()
#L = [int(input()) for i in range(N)]
A = inputl()
B = inputl()
C = inputl()
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=lambda x:x[1],reverse=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から最も左の4位置を返す。
#bisect.insort_left(a, 4)#挿入
A.sort(reverse=True)
B.sort()
C.sort()
tot=0
cut=N

for a in A:
    cut=bisect.bisect_right(B[0:cut], a)
    cut2=N
    for i in reversed(range(cut,N)):
        b=B[i]
        cut2=bisect.bisect_right(C[0:cut2], b)
        tot+=N-cut2
print(tot)

### FIXED CODE ###

import sys
#import math
#import queue
#import copy
import bisect#2分探索

def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())
def inputl():
    return list(map(int, input().split()))
def printl(li):
    print(*li, sep="\n")
def argsort(s):
    return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

N = inputi()
#N, K = inputl()
#L = [int(input()) for i in range(N)]
A = inputl()
B = inputl()
C = inputl()
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=lambda x:x[1],reverse=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から最も左の4位置を返す。
#bisect.insort_left(a, 4)#挿入


##TLE
# A.sort(reverse=True)
# B.sort()
# C.sort()
# tot=0
# cut=N
# for a in A:
#     cut=bisect.bisect_right(B[0:cut], a)
#     cut2=N
#     for i in reversed(range(cut,N)):
#         b=B[i]
#         cut2=bisect.bisect_right(C[0:cut2], b)
#         tot+=N-cut2

#right ans
tot=0
A.sort()
C.sort()
for b in B:
    cut1=bisect.bisect_left(A, b)
    cut2=bisect.bisect_right(C, b)
    tot+=cut1*(N-cut2)
print(tot)
### BUGGY CODE ###

n,m = (int(i) for i in input().split())
a = [int(input()) for i in range(m)]
oks = [True if not i in a else False for i in range(n+1)]
mod = 1000000007
dp = [0 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1 if not 1 in a else 0
for i in range(2,n+1):
    if oks[i] is True:
        dp[i] = (dp[i-1]+dp[i-2])%mod
print(dp[n])


### FIXED CODE ###

n,m = (int(i) for i in input().split())
a = [int(input()) for i in range(m)]
mod = 1000000007
oks = [True for _ in range(n+1)]
for i in a:
    oks[i] = False
dp = [1,0]
dp[1] = 1 if oks[1] is True else 0
for i in range(2,n+1):
    if oks[i] is True:
        dp.append((dp[i-1]+dp[i-2])%mod)
    else:
        dp.append(0)
print(dp[n])
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
tree = [[] for i in range(n)]
counter = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
for i in range(q):
    p, x = map(int, input().split())
    children = deque([p - 1])
    while children:
        c = children.pop()
        counter[c] += x
        for j in tree[c]:
            children.append(j)
print(*counter)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
tree = [[] for i in range(n)]
counter = [0] * n
visited = [False] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
    # tree[b - 1].append(a - 1)
for i in range(q):
    p, x = map(int, input().split())
    counter[p - 1] += x
queue = deque([0])
visited[0] = True
while queue:
    now = queue.pop()
    for j in tree[now]:
        if visited[j]:
            continue
        counter[j] += counter[now]
        visited[j] = True
        queue.append(j)
print(*counter)
### BUGGY CODE ###

#!python3

import sys
sys.setrecursionlimit(10 ** 6)

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
AB = [LI() for _ in range(M)]

# params
link = [[] for _ in range(N)]
for a, b in AB:
    link[a - 1].append(b - 1)
impossible = [False] * N
n = [N]


def joint(v, visit):
    if impossible[v]:
        return []
    visit = visit + [v]
    if len(visit) > n[0]:
        return []
    ans = []
    for u in link[v]:
        if u in visit:
            i = visit.index(u)
            return visit[i:]
        t = joint(u, visit)
        if 0 < len(t):
            if ans == [] or 0 < len(t) < n[0]:
                ans = t
                n[0] = len(ans)
    if ans == []:
        impossible[v] = True
    return ans


def main():
    ans = []
    for i in range(N):
        t = joint(i, [])
        if 0 < len(t):
            if ans == [] or 0 < len(t) < len(ans):
                ans = t
    if ans == []:
        print(-1)
        return
    print(len(ans))
    for x in ans:
        print(x + 1)
        

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!python3

import sys
sys.setrecursionlimit(10 ** 6)

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
AB = [LI() for _ in range(M)]

# params
link = [[] for _ in range(N)]
for a, b in AB:
    link[a - 1].append(b - 1)
impossible = [False] * N


def joint(v, visit):
    if impossible[v]:
        return None
    visit = visit + [v]
    for u in link[v]:
        if u in visit:
            i = visit.index(u)
            return visit[i:]
        t = joint(u, visit)
        if t is not None:
            return t
    impossible[v] = True
    return None


def solve(l):
    n = len(l)
    d = {l[i]: i for i in range(n)}
    for i in range(n):
        x = l[i]
        for y in link[x]:
            if y in d:
                j = d[y]
                if (i + 1) % n == j:
                    continue
                if j < i:
                    l = l[j : i + 1]
                else:
                    l = l[: i + 1] + l[j:]
                return solve(l)
    return l
            

def main():
    t = None
    for i in range(N):
        t = joint(i, [])
        if t is not None:
            break
    if t is None:
        print(-1)
        return
    
    ans = solve(t)
    print(len(ans))
    for x in ans:
        print(x + 1)
        

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

import math
n = int(input())
nlist = list(map(int,input().split()))
xlist = sorted(nlist)

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

count = 0
for i in range(1,len(nlist)+1):
    if nlist.count(i) >= 2:
        count+=combinations_count(nlist.count(i),2)

anslist = []

for i in range(0,len(xlist)):
    anslist.append(count-xlist.count(nlist[i])+1)

for i in anslist:
    print(i)

### FIXED CODE ###

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

import collections

count_dict=collections.Counter(nlist)

anslist=[]
all_kumi=0
for i in count_dict.values():
    all_kumi += i*(i-1)//2
 
for j in range(0,n):
    print(all_kumi - count_dict[nlist[j]] + 1)
### BUGGY CODE ###


N = int(input())
k = 0

while N > 0:
    k += N % 10
    N = N // 10

if k % 9 == 0:
    print("Yes")

else:
    print("No")




### FIXED CODE ###


N = list(input())
k = 0

for i in range(len(N)):
    N[i] = int(N[i])
    k += N[i]

if k % 9 == 0:
    print("Yes")

else:
    print("No")
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 9)
N,M,K=map(int,input().split())
As=list(map(int,input().split()))
Bs=list(map(int,input().split()))

def f(nb,s,ia,ib):
    #print(nb,s,ia,ib)
    if s > K:
        return nb-1
    if ia==N and ib==M:
        return nb
    
    nb_max=0
    for nxt in ['a','b']:
        if nxt == 'a':
            if ia==N:
                continue
            nb_max=f(nb+1,s+As[ia],ia+1,ib)
        if nxt == 'b':
            if ib==M:
                continue
            nb_tmp=f(nb+1,s+Bs[ib],ia,ib+1)
            if nb_max < nb_tmp:
                nb_max = nb_tmp
    return nb_max



ans = f(0,0,0,0)
print(ans)



### FIXED CODE ###

N,M,K=map(int,input().split())
As=list(map(int,input().split()))
Bs=list(map(int,input().split()))

a_sum=[0]
for i in range(N):
    a_sum.append(a_sum[-1]+As[i])

b_sum=[0]
for i in range(M):
    b_sum.append(b_sum[-1]+Bs[i])

j=M
ans=0
for i in range(N+1):
    if a_sum[i] > K:
        break

    while b_sum[j] > K - a_sum[i]:
        j-=1
    ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

import numpy as np
 
N, K, Q = map(int, input().split())
 
points = np.array([K for _ in range(N)])
 
for q in range(Q):
    A = int(input()) - 1
    points -= 1
    points[A] += 1
 
[print('Yes') if p > 0 else print('No') for p in points]

### FIXED CODE ###

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

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

points = np.array([K - Q for _ in range(N)])

for q in range(Q):
    A = int(input()) - 1
    points[A] +=1

for p in points:
    if p < 1:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

N = int(input())

for _ in range(N):
    x = input()
    y = input()
    m, n = len(x), len(y)
    dp = [0] * (n+1)
    
    for xi in x:
        temp = dp[:]
        for j in range(n):
            if xi == y[j]:
                dp[j+1] = temp[j] + 1
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]
                
    print(dp[-1])

### FIXED CODE ###

def lcs(s1, s2):
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if not chr_idx:
                break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if chr_idx:
                dp.append(chr_idx)
    return len(dp)

def solve():
    N = int(input())
    for _ in range(N):
        x = input()
        y = input()
        print(lcs(x, y))

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

n,q = map(int,input().split())
s = list(input())
lr_list = [0]*q
for i in range(q):
    l,r = map(int,input().split())
    lr_list[i] = s[l-1:r]
for i in lr_list:
    pre_s = "hoge"
    ans = 0
    for j in i:
        if pre_s == "A" and j == "C":
            ans += 1
        pre_s = j
    print(ans)

        
#print(lr_list)

### FIXED CODE ###

n,q = map(int,input().split())
s = "p" + str(input())
lr = [list(map(int,input().split())) for i in range(q)]
cnt = 0
ans = [0] * (n+1)
for i in range(1,n+1):
    if s[i-1] == "A" and s[i] == "C":
        cnt += 1
    ans[i] = cnt
for i in lr:
    print(ans[i[1]] - ans[i[0]])
### BUGGY CODE ###

from heapq import *
X, Y, Z, K = map(int, input().split())
candy = [[],[],[]]
for i in range(3):
    temp = list(map(int, input().split()))
    candy[i] = temp

for i in range(3):
    candy[i] = sorted(candy[i], reverse=True)

output = []
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            output.append(candy[0][i] + candy[1][j] + candy[2][k])
output = sorted(output, reverse=True)
for i in range(K):
    print(output[i])

### FIXED CODE ###

import heapq
X, Y, Z, K = map(int, input().split())
candy = [[],[],[]]
for i in range(3):
    temp = list(map(int, input().split()))
    candy[i] = temp

for i in range(3):
    candy[i] = sorted(candy[i], reverse=True)
i, j, k = 0, 0, 0
heap = [(-(candy[0][i] + candy[1][j] + candy[2][k]), i, j, k)]
cnt = 0
visit = {(i, j, k)}
while cnt < K:
    s, ii, jj, kk = heapq.heappop(heap)
    print(-s)
    cnt += 1
    if ii < len(candy[0]) - 1 and (ii+1, jj, kk) not in visit:
        heapq.heappush(heap, (-(candy[0][ii + 1] + candy[1][jj] + candy[2][kk]), ii + 1, jj, kk))
        visit.add((ii+1, jj, kk))
    if jj < len(candy[1]) - 1 and (ii, jj+1, kk) not in visit:
        heapq.heappush(heap, (-(candy[0][ii] + candy[1][jj + 1] + candy[2][kk]), ii, jj + 1, kk))
        visit.add((ii, jj+1, kk))
    if kk < len(candy[2]) - 1 and (ii, jj, kk+1) not in visit:
        heapq.heappush(heap, (-(candy[0][ii] + candy[1][jj] + candy[2][kk + 1]), ii, jj, kk + 1))
        visit.add((ii, jj, kk+1))
### BUGGY CODE ###

#インポート
import sys

#入力用
def ILI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def ISI(): return map(int, sys.stdin.readline().rstrip().split())
def II(): return int(sys.stdin.readline().rstrip())
def ISS(): return sys.stdin.readline().rstrip().split()
def IS(): return sys.stdin.readline().rstrip()

N = II()
A = [i for i in range(1, N+1)]
sum = sum(A)
print(sum-N)

### FIXED CODE ###

#インポート
import sys
 
#入力用
def ILI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def ISI(): return map(int, sys.stdin.readline().rstrip().split())
def II(): return int(sys.stdin.readline().rstrip())
def ISS(): return sys.stdin.readline().rstrip().split()
def IS(): return sys.stdin.readline().rstrip()
 
N = II()
sum = N*(1+N)//2
print(sum-N)
### BUGGY CODE ###

A,B=[int(x) for x in str(input()).split()]

X=[]
m=len(bin(B)[2:])
for j in range(A,B+1):
  temp=bin(j)[2:]
  for i in range(m-len(temp)):
    temp="0"+temp
  X.append(temp)

diff=B-A+1
t=diff%2
ans=""
for j in range(m-1):
  if t==0:
    if A%2==0:
      ans+="0"
    else:
      if X[0][j]==X[-1][j]:
        ans+="0"
      else:
        ans+="1"
  if t==1:
    if A%2==0:
      ans+=X[-1][j]
    else:
      ans+=X[0][j]

if diff%4==0:
  ans+="0"
elif diff%4==1:
  if A%2==0:
    ans+="0"
  else:
    ans+="1"
elif diff%4==2:
  ans+="1"
elif diff%4==3:
  if A%2==0:
    ans+="1"
  else:
    ans+="0"



print(int(ans,2))



### FIXED CODE ###

A,B=[int(x) for x in str(input()).split()]

X=[]
m=len(bin(B)[2:])
temp=bin(A)[2:]
for i in range(m-len(temp)):
  temp="0"+temp
X.append(temp)
X.append(bin(B)[2:])


diff=B-A+1
t=diff%2
ans=""
for j in range(m-1):
  if t==0:
    if A%2==0:
      ans+="0"
    else:
      if X[0][j]==X[-1][j]:
        ans+="0"
      else:
        ans+="1"
  if t==1:
    if A%2==0:
      ans+=X[-1][j]
    else:
      ans+=X[0][j]

if diff%4==0:
  ans+="0"
elif diff%4==1:
  if A%2==0:
    ans+="0"
  else:
    ans+="1"
elif diff%4==2:
  ans+="1"
elif diff%4==3:
  if A%2==0:
    ans+="1"
  else:
    ans+="0"



print(int(ans,2))
### BUGGY CODE ###


#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

N,W = map(int,input().split())
wv = int_mtx(N)

#f_inf = float("inf")
#dp = [f_inf]*N

# dp[i][w] = "番号 i 以下の商品でバッグの重さが w 以下になるように最適に詰めた場合"
dp = np.array([[0]*(W+1)]*(N+1))

for i in range(1,N+1):
    for w in range(1,W+1):
        if w-wv[i-1][0] >= 0:
            dp[i][w] = max(dp[i-1][w-wv[i-1][0]]+wv[i-1][1] , dp[i-1][w])
        else:
            dp[i][w] = dp[i-1][w]

print(dp[N][W])


### FIXED CODE ###

def e():
    import numpy as np

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

    dp = np.zeros(W+1, dtype=np.int64)

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

    print(dp[-1])


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

import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**20
eps = 10**-7

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

P = [tuple(map(int,readline().split())) for i in range(N)]

X = []
Y = []
for (xi,yi) in P:
    X.append(xi)
    Y.append(yi)
X.sort()
Y.sort()
from itertools import combinations

ans = INF
def count(xmin,xmax,ymin,ymax):
    ret = 0
    for (xi,yi) in P:
        if (xmin <= xi <= xmax) and (ymin <= yi <= ymax):
            ret += 1
    return ret

for (xmin,xmax) in combinations(X,2):
    for (ymin,ymax) in combinations(Y,2):
        if count(xmin,xmax,ymin,ymax) >= K:
            ans = min(ans,(xmax-xmin)*(ymax-ymin))
print(ans)



### FIXED CODE ###

import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**20
eps = 10**-7

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

P = [tuple(map(int,readline().split())) for i in range(N)]

X = []
Y = []
for (xi,yi) in P:
    X.append(xi)
    Y.append(yi)
X.sort()
Y.sort()
from itertools import combinations

ans = INF
def count(xmin,xmax,ymin,ymax):
    ret = 0
    for (xi,yi) in P:
        if (xmin <= xi <= xmax) and (ymin <= yi <= ymax):
            ret += 1
    return ret

for (xmin,xmax) in combinations(X,2):
    for (ymin,ymax) in combinations(Y,2):
        if count(xmin,xmax,ymin,ymax) >= K:
            ans = min(ans,(xmax-xmin)*(ymax-ymin))
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
    a.sort()
    a[n-1]/=2
a=[int(b) for b in a]
print(sum(a))

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]*=-1
heapq.heapify(a)
for i in range(m):
  heapq.heappush(a,(heapq.heappop(a)+1)//2)
print(-sum(a))
### BUGGY CODE ###

n = int(input())
l = [int(li) for li in input().split()]

ret = 0
clc = {}

for i in range(0, n - 2):
  for j in range(i + 1, n - 1):
    for k in range(j + 1, n):

      key = tuple(sorted((l[i], l[j], l[k])))

      if not key in clc.keys():
        clc[key] = (key[0] < key[1] + key[2]) and \
                   (key[2] < key[0] + key[1]) and \
                   (key[1] < key[2] + key[0])

      ret += clc[key]

print(ret)


### FIXED CODE ###

# a - b < c
# b - a < c
# a + b > c

import bisect

n = int(input())

l = sorted([int(li) for li in input().split()])
#print(l)

ret = 0

for i in reversed(range(0, n)):
  for j in reversed(range(0, i)):
    k = bisect.bisect_left(l, l[i] + l[j])
    k = n - k
    ret += (n - 1 - i) - k

print(ret)