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

import collections
def main():
    s=input()
    ans=0
    res=[0]*len(s)
    for i in range(len(s)):
        res[i]=int(s[len(s)-1-i:])%2019
    cnt=collections.Counter(res)
    for i in range(len(cnt)):
        ans+=cnt.most_common()[i][1]-1
        if cnt.most_common()[i][0]==0:
            ans+=1
    print(ans)
if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    import collections
    s=list(map(int,input()))
    modpow=[1]*len(s)
    for i in range(1,len(s)):
        modpow[i]=(modpow[i-1]*10)%2019
    ans=0
    res=[0]*len(s)
    res[0]=s[-1]%2019
    for i in range(1,len(s)):
        res[i]=(modpow[i]*s[len(s)-1-i]+res[i-1])%2019
    res.append(0)
    c=collections.Counter(res).most_common()
    for i in range(len(c)):
        ans+=(c[i][1]*(c[i][1]-1)//2)
    print(ans)
if __name__=="__main__":
    main()
### BUGGY CODE ###

from operator import mul
from functools import reduce

def main ():
  count = int(input())
  c = list(map(int,input().split()))

  if 0 in c:
    print(0)
    return

  a = reduce(mul, c)

  if a > 1000000000000000000:
    print(-1)
    return
  else:
    print(a)

main()

### FIXED CODE ###

def main ():
  count = int(input())
  c = list(map(int,input().split()))

  if 0 in c:
    print(0)
    return

  result = 1
  for a in c:
    result *= a
    if result > 1000000000000000000:
      print(-1)
      return

  print(result)

main()
### BUGGY CODE ###

max,n = map(int,input().split())
l = list(map(int,input().split()))

double = [ i + max for i in l]
ll = l + double

sum = 0
home = 0
ans = 9999999
for i in range(n):
    for j in range(n-1):
        sum += ll[i+j+1] - ll[i+j]
        #print('ll[i+j+1]%d  -  ll[i+j]%d= sum%d    i=%d  j=%d'%(ll[i+j+1],ll[i+j],sum,i,j))

    ans = sum if sum < ans else ans
    #ans = min(ans,sum)
    sum = 0
    
print(ans)

### FIXED CODE ###

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

ll = l[:]

ll.append(k)
ll.pop(0)
s = []
x = (l[0] + k) - l[-1]


for i,j in zip(l,ll):
    s.append(j - i)

print(k - max(s+[x]))
### BUGGY CODE ###

import bisect

N = int(input())
A = [int(input()) for _ in range(N)]


colors = []
for i in range(N):
    if i == 0:
        colors.append(A[i])
    else:
        # 上に積める色がないなら新しく追加
        if A[i] <= colors[0]:
            colors = [A[i]] + colors
        # 積む色がある場合
        else:
            idx = bisect.bisect_left(colors, A[i])
            colors[idx-1] = A[i]


print(len(colors))

### FIXED CODE ###

import bisect

N = int(input())
A = [int(input()) for _ in range(N)]


colors = []

#後ろから見ていく
for i,n in enumerate(list(reversed(A))):
    # 一つ目はとりあえずなんか一色ぬる
    if i == 0:
        colors.append(n)
    else:
        #二つ目以降は、各色の最小値のなかで、今見ているのより小さいものがあればそれを置き換える
        #ここをbisect_leftにすると、colorsの中で同じ最小値があるときにinsertが必要なので遅い
        # 「各色の最小値集合の最小値と置き換える」を繰り返すので、最小値集合の最大より大きいなら最後に追加
        idx = bisect.bisect_right(colors, n)
        if idx == len(colors):
            colors.append(n)
        else:
            colors[idx] = n

print(len(colors))
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
max_ans = 0
tmp_ans = 0
queue = []
for i in range(N):
    e = (p[i] + 1) / 2 
    queue.append(e)
    if len(queue) > K:
        tmp_ans = tmp_ans - queue.pop(0) + e
    else:
        tmp_ans += e
    max_ans = max(max_ans, tmp_ans)
print(max_ans)

### FIXED CODE ###

from collections import deque
N, K = map(int, input().split())
p = list(map(int, input().split()))
max_ans = 0
tmp_ans = 0
queue = deque([])
for i in range(N):
    e = (p[i] + 1) / 2 
    tmp_ans += e
    queue.append(e)
    if len(queue) > K:
        tmp_ans = tmp_ans - queue.popleft()
    max_ans = max(max_ans, tmp_ans)
print(max_ans)
### BUGGY CODE ###

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

MOD = 10**9+7

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

if S[0] == "W" or S[-2] == "W":
    print(0)
    sys.exit()

LR = [0]
for i in range(1, 2*N):
    if LR[i-1] == 0:
        if S[i] == S[i-1]:
            LR.append(1)
        else:
            LR.append(0)
    else:
        if S[i] == S[i-1]:
            LR.append(0)
        else:
            LR.append(1)

if LR.count(0) != N:
    print(0)
    sys.exit()

count0 = 0
ans = 1
for i in range(2*N):
    if LR[i] == 0:
        count0 += 1
    else:
        ans *= count0
        count0 -= 1

def factorial(N, mod):
    if N == 0 or N == 1:
        return 1
    else:
        return N * factorial(N-1, mod) % mod

print(ans*factorial(N,MOD)%MOD)

### FIXED CODE ###

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

MOD = 10**9+7

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

if S[0] == "W" or S[-1] == "W":
    print(0)
    sys.exit()

LR = [0 for i in range(2*N)]
count0 = 1
count0_raw = 1
ans = 1
for i in range(1, 2*N):
    if LR[i-1] == 0:
        if S[i] == S[i-1]:
            LR[i] = 1
        else:
            LR[i] = 0
    else:
        if S[i] == S[i-1]:
            LR[i] = 0
        else:
            LR[i] = 1

    if LR[i] == 0:
        count0 += 1
        count0_raw += 1
    else:
        ans *= count0
        ans %= MOD
        count0 -= 1

if count0_raw != N:
    print(0)
    sys.exit()

N_k = 1
for i in range(N):
    N_k *= i+1
    N_k %= MOD

print(ans*N_k%MOD)
### BUGGY CODE ###

import numpy as np
N = int(input())
S = input()

l_r = []
l_g = []
l_b = []
for i in range(N):
  if S[i]=='R':
    l_r.append(i)
  if S[i]=='G':
    l_g.append(i)
  if S[i]=='B':
    l_b.append(i)

ans = len(l_r)*len(l_g)*len(l_b)

for r in l_r:
  for g in l_g:
    mi = min(r, g)
    ma = max(r, g)
    l = ma - mi
    if ma+l in l_b:
      ans -= 1
    if mi-l in l_b:
      ans -= 1
    if l%2==0 and l//2 + mi in l_b:
      ans -= 1

print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
S = input()

l_r = set()
l_g = set()
l_b = set()
for i in range(N):
  if S[i]=='R':
    l_r.add(i)
  if S[i]=='G':
    l_g.add(i)
  if S[i]=='B':
    l_b.add(i)

ans = len(l_r)*len(l_g)*len(l_b)

for r in l_r:
  for g in l_g:
    mi = min(r, g)
    ma = max(r, g)
    l = ma - mi
    if ma+l in l_b:
      ans -= 1
    if mi-l in l_b:
      ans -= 1
    if l%2==0 and l//2 + mi in l_b:
      ans -= 1

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

n = int(input())
S = input()
cnt = 0
for i in range(1000):
  hy = i//100
  zyu = (i-hy*100)//10
  ichi = i%10
  cnt_hy = float('inf')
  cnt_zyu = float('inf')
  cnt_ichi = float('inf')
  t = 0
  for j in range(n):
    if int(S[j]) == hy and t == 0:
      cnt_hy = j
      t += 1
    elif int(S[j]) == zyu and t == 1:
      cnt_zyu = j
      t += 1
    elif int(S[j]) == ichi and t == 2:
      cnt_ichi = j
  if cnt_hy < cnt_zyu < cnt_ichi <= n-1:
    cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
S = input()
cnt = 0
for i in range(10):
  for j in range(10):
    for k in range(10):
      i_pos = S.find(str(i))
      if i_pos == -1:
        continue
      j_pos = S.find(str(j),i_pos+1)
      if j_pos == -1:
        continue
      k_pos = S.find(str(k),j_pos+1)
      if k_pos == -1:
        continue
      cnt += 1
print(cnt)
### BUGGY CODE ###

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

import sys


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


def resolve():
    n = int(input())
    s = input()

    all_count = 0
    count = 0
    for i in range(n):
        for j in range(i+1, n):
            if s[i] == s[j]:
                continue
            for k in range(j+1, n):
                if s[i] == s[k] or s[j] == s[k]:
                    continue
                if j - i != k - j:
                    count += 1

    print(count)


if __name__ == "__main__":
    resolve()



### FIXED CODE ###

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

import sys


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


def resolve():
    n = int(input())
    s = input()

    count_dic = {}

    for i in range(n):
        count_dic[str(i)+"R"] = s.count("R", i, n)
        count_dic[str(i)+"G"] = s.count("G", i, n)
        count_dic[str(i)+"B"] = s.count("B", i, n)

    all_count = n* (n-1) * (n-2)
    count = 0
    for i in range(n):
        for j in range(i+1, n):
            if s[i] == s[j]:
                continue

            if s[i] == "R" and s[j] == "G":
                target_str = "B"
            elif s[i] == "R" and s[j] == "B":
                target_str = "G"
            elif s[i] == "G" and s[j] == "R":
                target_str = "B"
            elif s[i] == "G" and s[j] == "B":
                target_str = "R"
            elif s[i] == "B" and s[j] == "R":
                target_str = "G"
            elif s[i] == "B" and s[j] == "G":
                target_str = "R"

            count += count_dic[str(j)+target_str]

            if 2*j-i < n:
                if target_str == s[2*j-i]:
                    count -= 1
            """
            for k in range(j+1, n):
                if j - i == k -j:
                    continue
                
                if s[i] == s[k] or s[j] == s[k]:
                    continue

                count += 1
            """

    print(count)


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

def main():
    import math
    from functools import lru_cache
    N = int(input())
    A = list(map(int, input().split()))
    tt = 0
    #ans = list()
    ann = 0
    memo = dict()

    def comb(m, n):
        return math.factorial(m) // (math.factorial(n) * math.factorial(m - n))
    '''
    def A_count(n):
        if n in memo:
            return memo[n]
        h = A.count(i)
        memo[n] = A.count(i)
        return h
    '''
    @lru_cache(maxsize = 1024)
    def annss(f):
        if f>=3:
            return (tt - comb(f, 2) + comb(f-1, 2))
        elif f==2:
            return tt - comb(f, 2)
        else:
            return tt
    

    B = set(A)
    for i in B:
        f = A.count(i)
        memo[i] = f
        if f>=2:
            tt = tt + comb(f, 2)

    for i in A:
        f = memo[i] #A_count(A[i])
        ann = annss(f)
        print(ann)

    #for i in ans:
    #    print(i)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import math
    import collections
    N = int(input())
    A = list(map(int, input().split()))
    tt = 0
    #ans = list()
    ann = 0

    def comb(m, n):
        #return math.factorial(m) // (math.factorial(n) * math.factorial(m - n))
        return ((m - 1 + 1) / 1) * (m - 2 + 1) / 2

    '''
    def A_count(n):
        if n in memo:
            return memo[n]
        h = A.count(i)
        memo[n] = A.count(i)
        return h
    '''

    C = collections.Counter(A)
    for i in C.values():
        if i>=2:
            tt = tt + comb(i, 2)

    for i in A:
        f = C[i] #A_count(A[i])
        if f>=3:
            ann = (tt - comb(f, 2) + comb(f-1, 2))
        elif f==2:
            ann = tt - comb(f, 2)
        else:
            ann = tt
        print(int(ann))

    #for i in ans:
    #    print(i)


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

from functools import reduce
from operator import mul
N = int(input())
An = input().split()
for i in range(N):
    An[i] = int(An[i])
AnS = reduce(mul,An)
if AnS <= 10**18:
    print(AnS)
else:
    print("-1")


### FIXED CODE ###

import sys
N = int(input())
An = list(map(int,input().split()))
a = 1
if 0 in An:
    print("0")
    sys.exit()
else:
    for i in range(N):
        a *= An[i]
        if a > 10**18:
            print("-1")
            sys.exit()
    if a <= 10**18:
        print(a)
        sys.exit()
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
cnt = 0
for i in range(n):
    if A[i] <= 0:
        cnt = cnt + 1
        A[i] = A[i]*(-1)
if cnt % 2 == 0:
    for a in A:
        ans = sum(A)
else:
    ans = sum(A) - 2*min(A)
print(ans)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
cnt = 0
s = 0
m = 10 ** 9
for ai in A:
    if ai <= 0:
        cnt = cnt + 1
        ai *= (-1)
    s += ai
    if m > ai:
        m = ai
if cnt % 2 == 0:
    for a in A:
        ans = s
else:
    ans = s - 2*m
print(ans)
### BUGGY CODE ###

import networkx

n, m = map(int, input().split())
g = networkx.Graph()
g.add_nodes_from(list(range(n)))
for i in range(1, m + 1):
    a, b = map(int, input().split())
    g.add_edge(a, b)
#print(g.nodes())
#print(g.edges())
print("Yes")
for i in range(2, n + 1):
    print(networkx.shortest_path(g, 1, i)[-2])

### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
a = [[] for _ in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    a[x - 1].append(y - 1)
    a[y - 1].append(x - 1)
c = [0] * n
que = deque([])
que.append(0)
while len(que) > 0:
    e = que.popleft()
    for i in a[e]:
        if c[i] > 0:
            continue
        c[i] = e + 1
        que.append(i)
print("Yes")
for i in range(1, n):
    print(c[i])
### BUGGY CODE ###

from collections import deque

def solve(d, g, pcs):
    queue = deque()
    queue.append((0, d, g, pcs, 0))
    while True:
        count, d, g, pcs, n = queue.popleft()
        #print(count, d, g, pcs)
        if g <= 0:
            return count
        if n > 0:
            p, c = pcs[n - 1]
            l = pcs.copy()
            if p == 1:
                l = pcs.copy()
                l[n - 1] = (0, 0)
                queue.append((count + 1, d, g - c - 100 * n, l, 0))
            elif p > 1:
                l = pcs.copy()
                l[n - 1] = (p - 1, c)
                queue.append((count + 1, d, g - 100 * n, l, n))
        else:
            for i in range(1, d + 1):
                p, c = pcs[i - 1]
                if p == 1:
                    l = pcs.copy()
                    l[i - 1] = (0, 0)
                    queue.append((count + 1, d, g - c - 100 * i, l, 0))
                elif p > 1:
                    l = pcs.copy()
                    l[i - 1] = (p - 1, c)
                    queue.append((count + 1, d, g - 100 * i, l, i))


if __name__ == "__main__":
    d, g = map(int, input().split())
    pcs = [tuple(int(s) for s in input().split()) for _ in range(d)]
    print(solve(d, g, pcs))


### FIXED CODE ###

from collections import deque

def solve(count, i, g, pcs, rem):
    if g <= 0:
        return count
    if pcs == []:
        index, p = rem
        if index == 0:
            return count
        plus = g // (100 * index) + (1 if g % (100 * index) != 0 else 0)
        return count + plus if plus < p else float("Inf")
    p, c = pcs[0]
    l = pcs[1:]
    a = solve(count, i + 1, g, l, (i, p))
    b = solve(count + p, i + 1, g - c - 100 * i * p, l, rem)
    return a if a < b else b



if __name__ == "__main__":
    d, g = map(int, input().split())
    pcs = [tuple(int(s) for s in input().split()) for _ in range(d)]
    print(solve(0, 1, g, pcs, (0, 0)))
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():

    class BinaryIndexedTree():
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(n+1)

        def add(self, item, pos):
            index = pos
            while index < self.n+1:
                self.bit[index] += item
                index += index & (-index)

        def sum(self, pos):
            ret = 0
            index = pos
            while index > 0:
                ret += self.bit[index]
                index -= index & -index
            return ret

    N = int(input())
    S = list(input())
    Q = int(input())
    Query = [input().split() for _ in range(Q)] 

    pos_bit_list = [BinaryIndexedTree(len(S)) for _ in range(26)]

    for i, c in enumerate(S):
        pos_bit_list[ord(c)-ord('a')].add(1, i+1)

    for q in Query:
        if q[0] == '1':
            pos_bit_list[ord(S[int(q[1])-1])-ord('a')].add(-1, int(q[1]))
            pos_bit_list[ord(q[2])-ord('a')].add(1, int(q[1]))
            S[int(q[1])-1] = q[2]
        else:
            print(len([p for p in pos_bit_list if p.sum(int(q[2])) - p.sum(int(q[1])-1) > 0]))

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():

    class BinaryIndexedTree():
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(n+1)

        def add(self, item, pos):
            index = pos
            while index < self.n+1:
                self.bit[index] += item
                index += index & (-index)

        def sum(self, pos):
            ret = 0
            index = pos
            while index > 0:
                ret += self.bit[index]
                index -= index & -index
            return ret

    N = int(input())
    S = list(input())
    Q = int(input())
    Query = [input().split() for _ in range(Q)] 

    pos_bit_list = [BinaryIndexedTree(len(S)) for _ in range(26)]

    for i, c in enumerate(S):
        pos_bit_list[ord(c)-ord('a')].add(1, i+1)

    for q in Query:
        if q[0] == '1':
            pos_bit_list[ord(S[int(q[1])-1])-ord('a')].add(-1, int(q[1]))
            pos_bit_list[ord(q[2])-ord('a')].add(1, int(q[1]))
            S[int(q[1])-1] = q[2]
        else:
            print(len([p for p in pos_bit_list if p.sum(int(q[2])) - p.sum(int(q[1])-1) > 0]))

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

# 全てを先に計算しておき、累積和を使って結果を表示する。
# それにより、同じ計算を何度もしなくてすむ。最大10^5になるはず。

import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


# 2017に似た数

def is_like2017(n):
    if is_prime(n) and is_prime((n+1)//2):
        return True
    else:
        return False


Q = int(input())

l_list = [0]*Q
r_list = [0]*Q

for i in range(Q):
    l_list[i], r_list[i] = map(int, input().split())
    
min_value = min(l_list)
max_value = max(r_list)

ans = []

for i in range(min_value, max_value+1):
    if i % 2 == 0:
        ans.append(0)
    elif is_prime(i) and is_like2017(i):
        ans.append(1)
    else:
        ans.append(0)

        
for i in range(Q):
    print(sum(ans[l_list[i]-min_value:r_list[i]-min_value+1]))


### FIXED CODE ###

# 全てを先に計算しておき、累積和を使って結果を表示する。 今度コソ累積和
# それにより、同じ計算を何度もしなくてすむ。最大10^5になるはず。
# 

import math
from itertools import accumulate

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


# 2017に似た数

def is_like2017(n):
    if is_prime(n) and is_prime((n+1)//2):
        return True
    else:
        return False


Q = int(input())

l_list = [0]*Q
r_list = [0]*Q

for i in range(Q):
    l_list[i], r_list[i] = map(int, input().split())
    
min_value = min(l_list)
max_value = max(r_list)

ans = []

for i in range(min_value, max_value+1):
    if i % 2 == 0:
        ans.append(0)
    elif is_prime(i) and is_like2017(i):
        ans.append(1)
    else:
        ans.append(0)

ans = [0] + list(accumulate(ans))        
        
for i in range(Q):
    print(ans[r_list[i]-min_value+1]-ans[l_list[i]-min_value])
### BUGGY CODE ###

from copy import deepcopy
n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = sum(a)
a1 = deepcopy(a)
for i in range(1, n):
    cur = x * i
    a2 = deepcopy(a1)
    for j in range(n):
        a1[n - j - 1] = min(a2[n - j - 1], a[n - i - j - 1])
        cur += a1[n - j - 1]
    ans = min(ans, cur)
print(ans)

### FIXED CODE ###

from copy import deepcopy
n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = sum(a)
a1 = deepcopy(a)
for i in range(1, n):
    cur = x * i
    a2 = deepcopy(a1)
    for j in range(n):
        a1[n - j - 1] = min(a2[n - j - 1], a[n - i - j - 1])
        cur += a1[n - j - 1]
    ans = min(ans, cur)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100001)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
visited = [False] * n
for _ in range(m):
    a, b = map(int, input().split())
    la = len(edges[a - 1])
    lb = len(edges[b - 1])
    edges[a - 1].append([b - 1, lb])
    edges[b - 1].append([a - 1, la])

def dfs(p, v):
    if visited[v]:
        return
    visited[v] = True
    for (i, r) in edges[v]:
        if i != p and r != -1:
            dfs(v, i)
    count = 0
    pr = -1
    for (i, r) in edges[v]:
        if i != p and r != -1:
            print(v + 1, i + 1)
            edges[i][r][1] = -1
            count += 1
        if i == p:
            pr = r
    if count % 2 == 1:
        print(v + 1, p + 1)
        edges[p][pr][1] = -1

if m % 2 == 1:
    print(-1)
else:
    dfs(-1, 0)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100001)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
visited = [False] * n
for _ in range(m):
    a, b = map(int, input().split())
    la = len(edges[a - 1])
    lb = len(edges[b - 1])
    edges[a - 1].append([b - 1, lb])
    edges[b - 1].append([a - 1, la])

def dfs(p, v):
    visited[v] = True
    for (i, r) in edges[v]:
        if not visited[i] and r != -1 and i != p:
            dfs(v, i)
    odd = False
    pr = -1
    for (i, r) in edges[v]:
        if i != p:
            if r != -1:
                edges[i][r][1] = -1
                odd = not odd
        else:
            pr = r
    if odd:
        edges[p][pr][1] = -1

if m % 2 == 1:
    print(-1)
else:
    dfs(-1, 0)
    for v in range(n):
        for (i, r) in edges[v]:
            if r >= 0:
                print(v + 1, i + 1)
### BUGGY CODE ###

from collections import defaultdict

def main():
    num, weigh = map(int, input().split())
    dp = [defaultdict(int) for i in range(num + 1)]
    dp[0][0] = 0

    for i in range(1, num + 1):
        data = list(map(int, input().split()))
        for pre_value in dp[i - 1].keys():
            dp[i][pre_value] = max(dp[i - 1][pre_value], dp[i][pre_value])
            if pre_value + data[0] <= weigh:
                dp[i][pre_value + data[0]] = max(dp[i - 1][pre_value] + data[1], dp[i][pre_value + data[0]])

    print(max(list(dp[-1].values())))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import numpy as np




def main():
    num, lim_weight = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]

    dp = np.full(10 ** 5 + 1, np.inf)

    for i in range(num):
        weight, value = data[i]
        prev = dp.copy()
        dp[:value] = np.minimum(prev[:value], weight)
        dp[value:] = np.minimum(prev[value:], prev[:-value] + weight)

        # print(dp[:100])
    ans = np.max(np.where(dp <= lim_weight)) + 1
    print(ans)

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

import sys
I = lambda:map(int,sys.stdin.readline().split())
pr = lambda x:sys.stdout.write(f'{x}\n')
sys.setrecursionlimit(2000000001)
ab = abs; mn = min
n = k = ar = dp = 0
 
def solve(x):
	global n,k,ar,dp
	if x>=n-2: return dp[x]
	if dp[x] != -1: return dp[x]
	m = 1e9
	for i in range(x+1,mn(n,x+k+1)):
		t = ab(ar[x]-ar[i])+solve(i)
		m = t if t<m else m
	dp[x] = m
	return dp[x]
 
def main():
	global n,ar,k,dp
	(n,k), ar = [[*map(int,s.split())] for s in [*open(0)]]
	dp = [-1]*(n-2) + [ab(ar[-2]-ar[-1]),0]
	pr(solve(0))
 
main()

### FIXED CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	# t = [ for i in range(x+1,mn(n,x+k+1))]
	t = map(lambda i:ab(ar[x]-ar[i])+solve(n,k,ar,dp,i), range(x+1,mn(n,x+k+1)))
	dp[x] = reduce(lambda a,b : a if a < b else b,t)
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(n,k,ar,dp,0))

main()
### BUGGY CODE ###

a,b = map(int, input().split())
ans = max([a,b])
while True:
    if (ans%a + ans%b) == 0:
        print(ans)
        break
    ans += 1

### FIXED CODE ###

ab = list(map(int, input().split()))
a = max(ab)
b = min(ab)
r = a%b
while r!=0:
    a = b
    b = r
    r = a%b
print(int(max(ab) * min(ab)/b))