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

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, Counter, deque
    from copy import copy

    n = int(readline())
    mat = [list(map(int, readline().split())) for _ in range(n)]

    edge = defaultdict(list)
    count = Counter()

    for x in range(1, n + 1):
        for j in range(n - 2):
            y = mat[x - 1][j]
            z = mat[x - 1][j + 1]
            uf, us = min(x, y), max(x, y)
            vf, vs = min(x, z), max(x, z)
            edge[(uf, us)].append((vf, vs))
            count[(uf, us)] += 0
            count[(vf, vs)] += 1

    ans = 0
    rem = n * (n - 1) // 2
    que = deque()
    for key, val in count.items():
        if val == 0:
            que.append(key)
    que_tomorrow = deque()

    while rem:
        ans += 1
        if not que:
            print(-1)
            return
        while que:
            cur_match = que.popleft()
            for nx_match in edge[cur_match]:
                count[nx_match] -= 1
                if count[nx_match] == 0:
                    que_tomorrow.append(nx_match)
            rem -= 1
            count[cur_match] = -1
        que = copy(que_tomorrow)
        que_tomorrow.clear()

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def calc_id(x, y):
        return min(x, y) * 10007 + max(x, y)

    from collections import defaultdict, Counter, deque
    from copy import copy

    n = int(readline())

    edge = defaultdict(list)
    count = Counter()

    for x in range(1, n + 1):
        a = list(map(int, readline().split()))
        count[calc_id(x, a[0])] += 0
        for j in range(n - 2):
            y = a[j]
            z = a[j + 1]
            u_id = calc_id(x, y)
            v_id = calc_id(x, z)
            edge[u_id].append(v_id)
            count[v_id] += 1

    ans = 0
    rem = n * (n - 1) // 2
    que = deque()
    for key, val in count.items():
        if val == 0:
            que.append(key)
    que_tomorrow = deque()

    while rem:
        ans += 1
        if not que:
            print(-1)
            return
        while que:
            cur_match = que.popleft()
            for nx_match in edge[cur_match]:
                count[nx_match] -= 1
                if count[nx_match] == 0:
                    que_tomorrow.append(nx_match)
            rem -= 1
        que = copy(que_tomorrow)
        que_tomorrow.clear()

    print(ans)


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

def main(n: int, a: list):
    ans = 0
    for i in range(n):
        t = a.copy()
        t[i] = 0

        print(max(t))


if __name__ == "__main__":
    n = int(input())
    a = [int(input()) for _ in range(n)]

    main(n, a)


### FIXED CODE ###

def main(n: int, a: list):
    a_max, a_second = sorted(a, reverse=True)[:2]

    for i in range(n):
        if a[i] != a_max:
            print(a_max)
        else:
            print(a_second)


if __name__ == "__main__":
    n = int(input())
    a = [int(input()) for _ in range(n)]

    main(n, a)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
yon = 0
for i in range(N):
    yon = K + A.count(i+1) - Q
    if yon > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
n = [K - Q] * N
for i in range(Q):
    n[A[i]-1] += 1
for i in range(N):
    if n[i] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

X = input()
X = X.replace("ST","")
if X[:len(X) // 2].count("S") == len(X) // 2:
    print(0)
    exit()
for i in range(10**5):
    note = X
    X = X.replace("ST","")
    if note == X:
        break
print(len(X))

### FIXED CODE ###

X = input()
stack = []
for e in X:
    if e == "S":
        stack.append(e)
    elif stack == []:
        stack.append(e)
    elif stack[-1] == "T":
        stack.append(e)
    elif stack[-1] == "S":
        stack.pop(-1)
print(len(stack))
### BUGGY CODE ###

n, k = map(int,input().split())
h = list(map(int,input().split()))
INF = float('inf')
dp = [INF] * n 
dp[0] = 0 
dp[1] = abs(h[1] - h[0])




for i in range(2,n):
    for j in range(1, min(i, k) + 1):
        dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i  -j]))
        

print(dp[n - 1])

            
        
        
        
        

### FIXED CODE ###

n, k = map(int,input().split())
h = list(map(int,input().split()))
INF = float('inf')
dp = [INF] * n 
dp[0] = 0 
dp[1] = abs(h[1] - h[0])




for i in range(2,n):
    for j in range(1, min(i, k) + 1):
        dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i  -j]))
        

print(dp[n - 1])
### BUGGY CODE ###

from operator import itemgetter

N = int(input())
l = [list(map(int, input().split())) for _ in range(N)]
ans = []
for i in range(N):
  l[i].append(l[i][0] - l[i][1])
  l[i].append(l[i][0] + l[i][1])
  del l[i][:2]
l.sort(key = itemgetter(1))
cnt = 0
for i in range(1, N):
  for j in range(i, -N, -1):
    if l[j-1][0] == - 10 ** 4:
      continue
    if l[i][0] < l[j-1][1]:
        l[i][0] = - 10 ** 4
        l[i][1] = - 10 ** 4
        cnt += 1
    break
print(N-cnt)

### FIXED CODE ###

from operator import itemgetter

N = int(input())
l = []
for i in range(N):
  a, b = map(int, input().split())
  s = [a-b, a+b]
  l.append(s)

l.sort(key = itemgetter(1))
cnt = 0
s = - 10 ** 10
for i in range(N):
  if l[i][0] >= s:
    s = l[i][1]
  else:
    cnt += 1
print(N-cnt)
### BUGGY CODE ###

N,M = map(int,input().split())
L = list(map(int,input().split()))
ans = 0
for i in range(N) :
    for j in range(i+1,N+1) :
        K = list(L[i:j])
        k = sum(K)
        if k % M == 0 :
            ans += 1
            #print(k)
print(ans)
    

### FIXED CODE ###

from collections import Counter

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

cums = [0]
for a in A:
    cums.append((cums[-1] + a) % M)

ctr = Counter(cums)

ans = 0
for v in ctr.values():
    ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

n,x,m=map(int,input().split())
a=[]
a.append(x*x%m)
ind=0
s=0
for i in range(m):
    t=a[i]*a[i]%m
    if a.count(t)==0:
        a.append(t)
    else:
        ind=a.index(t)
        break
s=sum(a[ind:])
l=len(a)-ind
loop_times = (n-1-ind)//l
answer=loop_times*s
for i in range((n-1-ind)%l):
    answer+=a[i+ind]
print(answer+x+sum(a[:ind]))

### FIXED CODE ###

# -*- coding: utf-8 -*-
N, X, M = map(int, input().split())

mod_check_list = [False for _ in range(M)]
mod_list = [(X ** 2) % M]
counter = 1
mod_sum = (X ** 2) % M
last_mod = 0
for i in range(M):
    now_mod = (mod_list[-1] ** 2) % M
    if mod_check_list[now_mod]:
        last_mod = now_mod
        break
    mod_check_list[now_mod] = True
    mod_list.append(now_mod)
    counter += 1
    mod_sum += now_mod

loop_start_idx = 0
for i in range(counter):
    if last_mod == mod_list[i]:
        loop_start_idx = i
        break

loop_list = mod_list[loop_start_idx:]
loop_num = counter - loop_start_idx
ans = 0
if mod_list[-1] == 0:
    ans = X + sum(mod_list[:min(counter, N - 1)])
else:
    if (N - 1) <= counter:
        ans = X + sum(mod_list[:N - 1])
    else:
        ans += X + mod_sum
        N -= (counter + 1)
        ans += sum(loop_list) * (N // loop_num) + sum(loop_list[:N % loop_num])
print(ans)
### BUGGY CODE ###

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

def calcScore(C_list, P_list, idx, num_operation):
  score = 0
  for i in range(num_operation):
    idx = P_list[idx] - 1
    score += C_list[idx]
    if i == 0:
      max_score = score
    else:
      max_score = max(max_score, score)
  return max_score

max_scores = [calcScore(Cs, Ps, i, K) for i in range(N)]

print(max(max_scores))
  
  

### FIXED CODE ###

N, K = map(int, input().split())
Ps = list(map(int, input().split()))
Ps = [i - 1 for i in Ps]
Cs = list(map(int, input().split()))
max_score = -float("inf")


for i in range(N):
    scores = []
    idx = i  # starting index
    while True:
        idx = Ps[idx]  # point to the next index
        scores.append(Cs[idx])  # fetch a score to add
        if idx == i:  # when the cycle is closed
            break

    len_cycle = len(scores)
    sum_cycle = sum(scores)

    if sum_cycle <= 0:  # when each cycle reduces the total score
        score = 0
        for j in range(min(K, len_cycle)):
            score += scores[j]
            max_score = max(max_score, score)
    else:
        if K // len_cycle > 0:
            num_multiply = K // len_cycle - 1
            score = sum_cycle * num_multiply
            scores = scores * 2
            for j in range(K % len_cycle + len_cycle):
                score += scores[j]
                max_score = max(max_score, score)
        else:
            num_multiply = 0  # len_cycle > K
            score = sum_cycle * num_multiply
            for j in range(K):
                score += scores[j]
                max_score = max(max_score, score)

print(max_score)
### BUGGY CODE ###

# python3
import sys

input = sys.stdin.readline


def main():
    # 2 <= N <= pow(10,5), 1 <= K <= 100
    N, K = [int(ele) for ele in input().split()]
    h = [Node(int(ele)) for ele in input().split()]

    for idx, n in enumerate(h):
        s = max(0, idx - K)
        n.parents = h[s:idx]
        n.cal_dp()

    print(h[-1].dp_val)


class Node():

    def __init__(self, val):
        self.val = val
        self.dp_val = 1000000000000
        self.parents = []

    def cal_dp(self):
        if self.parents == []:
            self.dp_val = 0
            return

        for n in self.parents:
            self.dp_val = min(self.dp_val, abs(n.val - self.val)+n.dp_val)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# python3
import sys

input = sys.stdin.readline


def main():
    # 2 <= N <= pow(10,5), 1 <= K <= 100
    N, K = [int(ele) for ele in input().split()]
    h = [Node(int(ele)) for ele in input().split()]

    for idx, n in enumerate(h):
        s = max(0, idx - K)
        n.parents = h[s:idx]
        n.cal_dp()

    print(h[-1].dp_val)


class Node():

    def __init__(self, val):
        self.val = val
        self.dp_val = 1000000000000
        self.parents = []

    def cal_dp(self):
        if self.parents == []:
            self.dp_val = 0
            return

        for n in self.parents:
            self.dp_val = min(self.dp_val, abs(n.val - self.val)+n.dp_val)


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

n = int(input())
p = []
for i in range(n):
    p.append(int(input()))
# x = [[1, 2, 4, 3], [2, 4, 1, 3], [2, 4, 3, 1], [4, 2, 1, 3], [4, 3, 2, 1]]
lens = []
for i in p:
    if i-1 not in lens:
        lens.append(i)
    else:
        lens[lens.index(i-1)] += 1
lens.sort()
x = 0
temp = 0
for i in lens:
    x = max(i-temp, x)
    temp = i
print(n-x)

### FIXED CODE ###

n = int(input())
lens = [False for i in range(n + 1)]

for i in range(n):
    p = int(input())
    lens[p] = True
    lens[p - 1] = False

ps = []
for i in range(n + 1):
    if lens[i]:
        ps.append(i)

ps.sort()
x = 0
temp = 0
for i in ps:
    x = max(i - temp, x)
    temp = i
print(n - x)
### BUGGY CODE ###

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

pair = n*(n - 1)/2
not_4 = 0

for i in range(len(a)):
  for j in range(len(a)):
    
    if i == j:
      continue
      
    if a[i]*a[j]%4 != 0:
      not_4 += 1
    
if pair > not_4:
  print('Yes')
else:
  print('No')
  

### FIXED CODE ###

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

four = 0
two = 0
one = 0
for i in a:
  if i%4 == 0:
    four += 1
  elif i%2 == 0 and i%4 != 0:
    two += 1
  elif i%2 != 0:
    one += 1

if four >= one or four + 1 >= two//2 + two%2 + one or n == two:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

from operator import itemgetter
from heapq import heappush,heappop
N = int(input())
table=[]
for i in range(N):
    a,b = map(int,input().split())
    table.append([a,b,i])
A = sorted(table,key=itemgetter(0))
B = sorted(table,key=itemgetter(1))

graph=[[] for i in range(N)]
for k in range(N-1):#距離、点
    graph[A[k][2]].append([abs(A[k][0]-A[k-1][0]),A[k-1][2]])
    graph[A[k][2]].append([abs(A[k][0]-A[k+1][0]),A[k+1][2]])
graph[A[N-1][2]].append([abs(A[N-1][0]-A[N-2][0]),A[N-2][2]])
for k in range(N-1):
    graph[B[k][2]].append([abs(B[k][1]-B[k-1][1]),B[k-1][2]])
    graph[B[k][2]].append([abs(B[k][1]-B[k+1][1]),B[k+1][2]])
graph[B[N-1][2]].append([abs(B[N-1][1]-B[N-2][1]),B[N-2][2]])
#プリム法
kei = []
visit=[False]*N
heappush(kei,[0,0])#距離,点
dist = 0
while kei:
    d,i = heappop(kei)
    if visit[i]==True:
        continue
    visit[i]=True
    dist += d
    for e,j in graph[i]:
        if not visit[j]:
            heappush(kei,[e,j])
print(dist)

### FIXED CODE ###

from operator import itemgetter
from heapq import heappush,heappop
N = int(input())
table=[]
for i in range(N):
    a,b = map(int,input().split())
    table.append([a,b,i])
A = sorted(table,key=itemgetter(0))
B = sorted(table,key=itemgetter(1))

graph=[]
for k in range(N):#距離、点
    graph.append([min(abs(A[k][0]-A[k-1][0]),abs( A[k][1]-A[k-1][1])),A[k][2],A[k-1][2]])
for k in range(N):
    graph.append([min(abs(B[k][0]-B[k-1][0]),abs( B[k][1]-B[k-1][1])),B[k][2],B[k-1][2]])

class Unionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)

    def find(self,x):#親を探す xの親を示す
        if self.par[x] ==x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self,x,y):#x,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
        else:
            self.par[py]=px
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)
#クラスカル法
kei = Unionfindtree(N)
graph.sort()
dist =0
for d,i,j in graph:
    if not kei.connect(i,j):
        kei.union(i,j)
        dist +=d
print(dist)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    S = list(input())
    N = len(S)
    A = [1] * N
    for _ in range(N//2+1):
        for i in range(N - 1):
            if S[i] == 'R' and S[i + 1] == 'R':
                A[i + 2] += A[i]
                A[i] = 0
        for i in range(N - 1, 0, -1):
            if S[i] == 'L' and S[i - 1] == 'L':
                A[i - 2] += A[i]
                A[i] = 0
    print(*A)


resolve()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    S = list(input())
    N = len(S)
    A = [1] * N
    for i in range(N - 1):
        if S[i] == 'R' and S[i + 1] == 'R':
            A[i + 2] += A[i]
            A[i] = 0
    for i in range(N - 1, 0, -1):
        if S[i] == 'L' and S[i - 1] == 'L':
            A[i - 2] += A[i]
            A[i] = 0
    print(*A)


resolve()
### BUGGY CODE ###

s = input()
l = len(s)
for i in range(l//2):
    s = s.replace("01","").replace("10","")
print(l-len(s))

### FIXED CODE ###

s = input()
l = len(s)
print(l-abs(s.count("1")-s.count("0")))
### BUGGY CODE ###

import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


n, k = LI()
a = LI()
base = 1
for elem in a[:k]:
    base *= elem
for i in range(k, n):
    now = (base//a[i - k]) * a[i]
    if base < now:
        ans = 'Yes'
    else:
        ans = 'No'
    base = now
    print(ans)


### FIXED CODE ###

import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


n, k = LI()
a = LI()
base = 1
for i in range(k, n):
    rate = a[i] / a[i-k]
    if rate > 1:
        ans = 'Yes'
    else:
        ans = 'No'
    print(ans)
### BUGGY CODE ###

n = int(input())

d = {}
for i in range(n):
    s = str(input())
    if s in d:
        d[s] += 1
    else:
        d[s] = 1

for i in sorted(k for k in d if d[k] == max(d.values())):
    print(i)

### FIXED CODE ###

n = int(input())

d = {}
for i in range(n):
    s = input()
    if s in d:
        d[s] += 1
    else:
        d[s] = 1

m = max(d.values())
for i in sorted(k for k in d if d[k] == m):
    print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = [int(input()) for _ in range(n)]
ans=max(a)
for i in range(n):
    print(ans if a[i]!=ans else sorted(a)[-2])

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = [int(input()) for _ in range(n)]
ans=max(a)
if a.count(ans)>1:
    for _ in range(n):
        print(ans)
else:
    for i in range(n):
        print(ans if a[i]!=ans else sorted(a)[-2])
### BUGGY CODE ###

from itertools import permutations

INF = 1e+9
N, M, R = map(int, input().split())
rlist = list(map(int, input().split()))

G = [[INF]*N for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    G[a-1][b-1] = G[b-1][a-1] = c

def warshall_floyd(G):
    V = len(G)
    for k in range(V):
        for i in range(V):
            for j in range(V):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    return G

G = warshall_floyd(G)
sum_list = []
for tmp in permutations(rlist):
    t_sum = 0
    for i in range(len(tmp)-1):
        t_sum += G[tmp[i]-1][tmp[i+1]-1]
    sum_list.append(t_sum)

print(min(sum_list))

### FIXED CODE ###

from itertools import permutations

INF = 1e+9
N, M, R = map(int, input().split())
rlist = list(map(int, input().split()))

G = [[INF]*N for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    G[a-1][b-1] = G[b-1][a-1] = c

def warshall_floyd(G):
    V = len(G)
    for k in range(V):
        for i in range(V):
            for j in range(V):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    return G

G = warshall_floyd(G)
sum_list = []
for tmp in permutations(rlist):
    t_sum = 0
    for i in range(len(tmp)-1):
        t_sum += G[tmp[i]-1][tmp[i+1]-1]
    sum_list.append(t_sum)

print(min(sum_list))
### BUGGY CODE ###

import re
s = input()
l = []
for i in range(len(s)+1):
    left = s[:i]
    right = s[i:]
    ml = re.match('<+',left[::-1])
    num = 0
    if ml:
        num = ml.end()
    mr = re.match('>+',right)
    if mr:
        num = max(num,mr.end())
    l.append(num)
#print(l)
print(sum(l))

### FIXED CODE ###

s = input().replace('><','> <').split()
ans = 0
#print(list(s))
for st in s:
    lt = st.count('<')
    gt = len(st) - lt
    if lt > gt:
        gt -= 1
    else:
        lt -= 1
    ans += (lt*lt+lt)//2 + (gt*gt+gt)//2
print(ans)
### BUGGY CODE ###

import math
from functools import reduce
from itertools import product

def gcd_(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

ans = 3*K*(K-1) + 1

for i,j,k in product(range(2,K+1),range(2,K+1),range(2,K+1)):
    ans += gcd_(i,j,k)

print(ans)

### FIXED CODE ###

import math
from functools import reduce
from itertools import product,combinations_with_replacement

def gcd_(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

ans = 3*K*(K-1) + 1

# for i,j,k in product(range(2,K+1),repeat=3):
#     ans += gcd_(i,j,k)
for i,j,k in combinations_with_replacement(range(2,K+1),3):
    if i==j and j==k:
        ans += i
    elif i==j or j==k or k==i:
        ans += gcd_(i,j,k) * 3
    else:
        ans += gcd_(i,j,k)*6
# for i in range(2,K+1):
#     for j in range(2,K+1):
#         for k in range(2,K+1):
#             ans += gcd_(i,j,k)

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

def is_ok(n):
    global N
    return n*(n+1)//2>=N
def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok
N = int(input())
n = meguru_bisect(0,10**7)
s = list(range(1, n+1))
import itertools
for i in itertools.product([0,1], repeat=n):
    a = [s[j-1] for j in s if i[j-1]]
    if sum(a) == N:
        for k in a:
            print(k)
        exit()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def is_ok(m, n):
    return m*(m+1)//2>=n
def meguru_bisect(ng, ok, n):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, n):
            ok = mid
        else:
            ng = mid
    return ok
def f(n):
    if n>0:
        m = meguru_bisect(0,10**7, n)
        print(m)
        f(n-m)
N = int(input())
f(N)
### BUGGY CODE ###

"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_d

D - Knapsack 1
"""
INF = 100000007


def solve(wv_pairs):
    dp = [0] * (W + 1)
    for i in range(N):
        w_i, v_i = wv_pairs[i]
        for ww in range(W, w_i - 1, -1):
            dp[ww] = max(dp[ww], dp[ww - w_i] + v_i)
    return max(dp[ww] for ww in range(W + 1))


N, W = map(int, input().split())
pairs = [[int(s) for s in input().split()] for _ in range(N)]
res = solve(pairs)
print(res)


### FIXED CODE ###

"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_d

D - Knapsack 1
"""

def solve(wv_pairs):
    dp = [0] * (W + 1)
    for i in range(N):
        w_i, v_i = wv_pairs[i]
        for ww in range(W, w_i - 1, -1):
            dp[ww] = max(dp[ww], dp[ww - w_i] + v_i)
    return max(dp)


N, W = map(int, input().split())
pairs = [[int(s) for s in input().split()] for _ in range(N)]
res = solve(pairs)
print(res)
### BUGGY CODE ###

n,m = map(int,input().split())
l = []
r = []
for i in range(m):
  A, B = list(map(int,input().split()))
  l.append(A)
  r.append(B)
sum = 0
for i in range(1,n+1,1):
  tmp = 0
  for j in range(m):
    if i >= l[j] and i <= r[j]:
      tmp += 1
  if tmp == m:
    sum += 1
print(sum)

### FIXED CODE ###

n,m = map(int,input().split())
l = []
r = []
for i in range(m):
  A, B = list(map(int,input().split()))
  l.append(A)
  r.append(B)

min = 0
max = n
for i in range(m):
  if min < l[i]:
    min = l[i]
  if max > r[i]:
    max = r[i]

if max - min + 1 > 0:
  print(max - min + 1)
else:
  print(0)
### BUGGY CODE ###

n, W = map(int, input().split())
obj = [list(map(int, input().split())) for _ in range(n)]
DP = [[0]*2*W for _ in range(n+1)]

for i in range(1, n+1):
    for w in range(W+1):
        weight, value = obj[i-1]
        DP[i][w] = max(DP[i-1][w], DP[i][w])
        if w + weight <= W:
            DP[i][w + weight] = max(DP[i - 1][w] + value, DP[i][w + weight])

ans = max(DP[n])
print(ans)

### FIXED CODE ###

n, W = map(int, input().split())
obj = [list(map(int, input().split())) for _ in range(n)]
DP = [[0]*2*W for _ in range(n+1)]

for i in range(1, n+1):
    for w in range(W+1):
        weight, value = obj[i-1]
        DP[i][w] = max(DP[i-1][w], DP[i][w])
        if w + weight <= W:
            DP[i][w + weight] = max(DP[i - 1][w] + value, DP[i][w + weight])

ans = max(DP[n])
print(ans)
### BUGGY CODE ###

import numpy as np
n,k = map(int,input().split())
ary = np.array(list(map(int,input().split())))
dp = np.zeros(n)
for i in range(1,n):
    a = max(0,i-k)
    dp[i] = min(dp[a:i]+np.abs(ary[i]-ary[a:i]))
print(int(dp[n-1]))

### FIXED CODE ###

import numpy as np

n, k = map(int,input().split())
h = list(map(int,input().split()))

h = np.array(h)
dp = np.zeros(n, dtype=int)

for i in range(1,n):
    m = max(0,i-k)
    dp[i] = min(dp[m:i] + np.abs(h[i] - h[m:i]))
print(dp[n-1])