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

H, W , D = map(int, input().split())
fields = []
X = []
for i in range(H):
    # fields.append(list(map(int, input().split())))
    X.extend(list(map(int, input().split())))
pairs = [(x-1,i) for i,x in enumerate(X)]
pairs.sort()
# print(pairs)
def calc_dist(a,b):
    return abs(a//W-b//W) + abs(a%W-b%W)

Q = int(input())
for i in range(Q):
    L1,R1 = map(int, input().split())
    ans = 0
    for i in range(L1,R1,D):
        a = pairs[i-1][1]
        b = pairs[i+D-1][1]
        ans += calc_dist(a,b)
        # print(i,a,b,ans)
    print(ans)
        


### FIXED CODE ###

H,W,D = map(int, input().split())
fields = []
amaris = [[0] * (H*W//D+1) for i in range(D)] # あまり
for i in range(H):
    row = list(map(int, input().split()))
    # あまりがいくつかで分類
    for j,e in enumerate(row):
        n = (e-1) // D
        m = (e-1) % D
        amaris[m][n] = (i,j)

# あまりごとに累積和を取っておく
acc = [[0] * (H*W//D+1) for i in range(D)]
for i in range(D):
    cnt = 0
    x_pre, y_pre = amaris[i][0]
    for j in range(1,(H*W)//D+1):
        coords = amaris[i][j]
        if isinstance(coords,int): break
        x = coords[0]
        y = coords[1]
        cnt += abs(x-x_pre)+abs(y-y_pre)
        acc[i][j] = cnt
        x_pre = x
        y_pre = y
# print(acc)

Q = int(input())
for i in range(Q):
    l,r  = map(int, input().split())
    m = (l-1) % D
    s = (l-1) // D
    g = (r-1) // D
    ans = acc[m][g] - acc[m][s]
    print(ans)
### BUGGY CODE ###

"""
A = 3, B = 4
[青青青][赤赤赤赤][青青青][赤赤赤]...

N = 8
[青青青赤赤赤赤青]

return 青 = 4
"""

def count_balls():
    # 入力
    N, A, B = map(int, input().split())
    # 例外
    if N > (A+B) * (10 ** 100):
        return A * (10 ** 100)
    # N以下の[青*A][赤*B]の組み合わせの個数
    i = 1
    while True:
        if N >= (A+B) * i:
            i += 1
        else:
            break
    # N - ([青*A]+[赤*B])*i
    remainder = N - (A+B) * (i-1)
    if remainder <= A:
        return A * (i-1) + remainder
    else:
        return A * (i-1) + A

result = count_balls()
print(result)

### FIXED CODE ###

"""
A = 3, B = 4
[青青青][赤赤赤赤][青青青][赤赤赤]...

N = 8
[青青青赤赤赤赤青]

return 青 = 4
"""

def count_balls():
    # 入力
    N, A, B = map(int, input().split())
    # [青青青赤赤赤赤]の個数と余り
    comb_count = N // (A + B)
    remainder = N % (A + B)
    # 集計
    if remainder <= A:
        return A * comb_count + remainder
    else:
        return A * comb_count + A

result = count_balls()
print(result)
### BUGGY CODE ###

#!/usr/bin/env python3


def solve(S: str):
    if len(S) < 4:
        return 0
    answer = 0
    for l in range(0, len(S) - 3):
        for r in range(l + 4, len(S) + 1):
            answer += int(S[l:r]) % 2019 == 0
    return answer


def main():
    S = input().strip()
    answer = solve(S)
    print(answer)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import numpy as np
from collections import Counter

YEAR = 2019


def solve(S: str):
    # S の各桁を modYear 計に修正する
    mod_year = np.arange(1, 10)
    mod_s = []
    for Si in map(int, reversed(S)):
        mod_s.append(mod_year[Si - 1])
        mod_year = (mod_year * 10) % YEAR
    #print(mod_s)
    # mod_s を累積和にする
    cum_sum = 0
    cum_sums = [cum_sum]
    for x in mod_s:
        cum_sum = (cum_sum+x) % YEAR
        cum_sums.append(cum_sum)

    answer = 0
    for _, num in Counter(cum_sums).items():
        answer += (num * (num-1)) // 2   # 1 の時0なので場合分けはいらない
    return answer


def main():
    S = input().strip()
    answer = solve(S)
    print(answer)


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

text_list = input().split()
n = 0
a = int(text_list[0])
b = int(text_list[0]) + int(text_list[1])
c = int(text_list[0]) + int(text_list[1]) + int(text_list[2])
for i in range(int(text_list[3])):
    if i < a:
        n += 1
    elif i < b:
        continue
    elif i < c:
        n -= 1

print(n)

### FIXED CODE ###

a, b, c, d = map(int, input().split())
if d <= a:
  print(d)
elif d <= a + b:
  print(a)
else:
  print(a-(d-(a+b)))
### BUGGY CODE ###

from itertools import combinations_with_replacement
import numpy as np 
N,M,Q = (int(x) for x in input().split())
abcd =np.zeros((Q,4),dtype=int)
for i in range(Q):
    abcd[i] = list(map(int, input().split()))
abcd[:,0] -=1 #添え字にするから、-1
abcd[:,1] -=1 #添え字にするから、-1

#リストAを要素数N,最大値Mで全列挙
ans =[]
#for i in range(1,N+1):
for a in combinations_with_replacement (range(1,M+1),N):
    co_np =[]
    for q in range(Q):
        A =list(a)
        #print(A,end=" ")
        if A[abcd[q,1] ] -A[abcd[q,0]] ==abcd[q,2]:
            co_np.append(abcd[q,3])
    ans.append(sum(co_np))
print(max(ans))

### FIXED CODE ###

#数列Aの取りうるものをcombinations_with_replacementで作って、全探索
#データ入力
from itertools import combinations_with_replacement
N,M,Q = (int(x) for x in input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]

#
all_A =[i for i in range(1,M+1)] #数列Aの取りうる値
A =[0]*N
ans =[]
for A in combinations_with_replacement(all_A,N):
    count =0
    for i in range(Q):
        ai,bi,ci,di =abcd[i]
        if A[bi-1] -A[ai-1] ==ci:
            count += di
    ans.append(count)
print(max(ans))
### BUGGY CODE ###

N,K = map(int,input().split())
a = list(map(int,input().split()))
b = set(a)
c = []
d = len(b)
ans = 0
for i in b:
  c.append(a.count(i))
c.sort()
for i in c:
  if K >= d:
    break
  ans += i
  d -= 1
print(ans)
  
  


### FIXED CODE ###

import sys
import collections
input = sys.stdin.readline

N,K = map(int,input().split())
a = list(map(int,input().split()))
c = collections.Counter(a)
d = len(c)
ans = 0
c_sorted = sorted(c.items(),key = lambda x:x[1])
for i in c_sorted:
    if K >= d:
        break
    ans += i[1]
    d -= 1
print(ans)
### BUGGY CODE ###

from bisect import bisect_left
import numpy as np

N, M, *A = map(int, open(0).read().split())
A.sort()


def calc(t):
    cnt = 0
    for ai in A:
        cnt += N - bisect_left(A, t - ai)
    if M <= cnt:
        return True
    else:
        return False


def solve():
    left, right = 0, 2 * 10 ** 5 + 1
    while 1 < right - left:
        mid = (left + right) // 2
        if calc(mid):
            left = mid
        else:
            right = mid
    
    sum_A = [0 for _ in range(N)]
    for i in range(N):
        sum_A[i] = np.cumsum(A[i:])[-1]
    
    ans = 0
    add_cnt = 0
    for ai in A:
        index = bisect_left(A, left - ai)
        if index == N:
            continue
        add_cnt += N - index
        ans += (N - index) * ai + sum_A[index]
    ans -= left * (add_cnt - M)
    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

from bisect import bisect_left

N, M, *A = map(int, open(0).read().split())
A.sort()


def calc(t):
    cnt = 0
    for ai in A:
        cnt += N - bisect_left(A, t - ai)
    if M <= cnt:
        return True
    else:
        return False


def solve():
    left, right = 0, 2 * 10 ** 5 + 1
    while 1 < right - left:
        mid = (left + right) // 2
        if calc(mid):
            left = mid
        else:
            right = mid
    
    sum_A = [0] * N
    sum_A[-1] = A[-1]
    for i in range(N - 2, -1, -1):
        sum_A[i] = sum_A[i + 1] + A[i]
    
    ans = 0
    add_cnt = 0
    for ai in A:
        index = bisect_left(A, left - ai)
        if index == N:
            continue
        add_cnt += N - index
        ans += (N - index) * ai + sum_A[index]
    ans -= left * (add_cnt - M)
    print(ans)


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

n,k=map(int,input().split())
p=list(map(int,input().split()))
max=0
for i in range(n-k+1):
    sum=0
    for j in range(i,i+k):
         sum+=p[j]
    if sum>max:
        max=sum
ans=(max+k)*0.5
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
max=0
sum=0
for i in range(0, k):
    sum += p[i]
max=sum
for i in range(1,n-k+1):
    sum+=p[k-1+i]-p[i-1]
    if sum>max:
        max=sum
ans=(max+k)*0.5
print(ans)
### BUGGY CODE ###

import math

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

mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
a_reverse = a[::-1]

plus = 0
minus = 0
cnt = 0
ind = 0
# ceil = nCr(n, k)
kaisu = nCr(n, k-1)
# while cnt < ceil:
for _ in range(n-k+1):
    kaisu = kaisu * ((n-ind)-(k-1)) // (n-ind)
    cnt += kaisu
    plus = (plus + (kaisu * a_reverse[ind]) % mod) % mod
    minus = (minus + (kaisu * a[ind]) % mod) % mod
    ind += 1

print((plus-minus) % mod)

### FIXED CODE ###

n,k = map(int, input().split())
a = sorted(list(map(int, input().split())))
a_reverse = a[::-1]
mod = 10**9+7
 
factorial = [1]
inverse = [1]
for i in range(1, n+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))
 
def comb(n, r, mod):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod

plus = 0
minus = 0
cnt = 0
ind = 0
for i in range(n-k+1):
    kaisu = comb(n-i-1, k-1, mod)
    plus = (plus + (kaisu * a_reverse[ind]) % mod) % mod
    minus = (minus + (kaisu * a[ind]) % mod) % mod
    ind += 1

print((plus-minus) % mod)
### BUGGY CODE ###

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

for i in range(3):
    a[i].sort()

dataa = []
datab = []
memo = 0
for i in range(N):
    flag = 0
    for j in range(0, N):
        if a[0][i] < a[1][j]:
            memo = i
            dataa.append(N - j)
            flag = 1
            break
    if flag == 0:
        dataa.append(0)
memo = 0
for i in range(N):
    flag = 0
    for j in range(0, N):
        if a[1][i] < a[2][j]:
            memo = i
            datab.append(N - j)
            flag = 1
            break
    if flag == 0:
        datab.append(0)
ruiseki = []
count = 0
for i in range(len(datab)-1, -1, -1):
    count += datab[i]
    ruiseki.append(count)
count2 = 0
for i in range(len(dataa)):
    if dataa[i] != 0:
        count2 += ruiseki[dataa[i] - 1]



print(count2)


### FIXED CODE ###

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

for i in range(3):
    a[i].sort()

dataa = []
datab = []
memo = 0
#print(a)
for i in range(N):
    flag = 0
    for j in range(memo, N):
        #print(a[0][i], a[1][j])
        if a[0][i] < a[1][j]:
            memo = j
            dataa.append(N - j)
            flag = 1
            break
    if flag == 0:
        for j in range(N - i):
            dataa.append(0)
        break
memo = 0
for i in range(N):
    flag = 0
    for j in range(memo, N):
        if a[1][i] < a[2][j]:
            memo = j
            datab.append(N - j)
            flag = 1
            break
    if flag == 0:
        for j in range(N - i):
            datab.append(0)
        break
ruiseki = []
count = 0
for i in range(len(datab)-1, -1, -1):
    count += datab[i]
    ruiseki.append(count)
count2 = 0
for i in range(len(dataa)):
    if dataa[i] != 0:
        count2 += ruiseki[dataa[i] - 1]



print(count2)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    x, y = zip(*(
        map(int, input().split())
        for _ in range(N)
    ))

    f(N, K, x, y)


def f(N, K, x, y):
    ans = abs(max(x) - min(x)) * abs(max(y) - min(y))
    if K == N:
        print(ans)
        return

    def r(x, y, x_start=0, y_start=0):
        for xi in range(x_start, N):
            for yi in range(y_start, N):
                yield x[xi], y[yi], xi, yi

    # for x1, y1 in zip(x, y):
    #     for x2, y2 in zip(x, y):
    # for x1, y1 in r(x, y):
    #     for x2, y2 in r(x, y):
    sorted_x = sorted(x)
    sorted_y = sorted(y)
    for min_x, min_y, xi, yi in r(sorted_x, sorted_y):
        for max_x, max_y, _, _ in r(sorted_x, sorted_y, x_start=xi+1, y_start=yi+1):

            # s = abs(x1-x2) * abs(y1-y2)
            # if s == 0:
            #     continue

            # min_x = min(x1, x2)
            # max_x = max(x1, x2)
            # min_y = min(y1, y2)
            # max_y = max(y1, y2)

            contains_count = 0
            for x3, y3 in zip(x, y):
                if min_x <= x3 <= max_x and min_y <= y3 <= max_y:
                    contains_count += 1
            if contains_count >= K:
                s = (max_x - min_x) * (max_y - min_y)
                ans = min(ans, s)

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    x, y = zip(*(
        map(int, input().split())
        for _ in range(N)
    ))

    f(N, K, x, y)


def f(N, K, x, y):
    ans = abs(max(x) - min(x)) * abs(max(y) - min(y))
    if K == N:
        print(ans)
        return

    def r(x, y, x_start=0, y_start=0):
        for xi in range(x_start, N):
            for yi in range(y_start, N):
                yield x[xi], y[yi], xi, yi

    # for x1, y1 in zip(x, y):
    #     for x2, y2 in zip(x, y):
    # for x1, y1 in r(x, y):
    #     for x2, y2 in r(x, y):
    sorted_x = sorted(x)
    sorted_y = sorted(y)
    for min_x, min_y, xi, yi in r(sorted_x, sorted_y):
        for max_x, max_y, _, _ in r(sorted_x, sorted_y, x_start=xi+1, y_start=yi+1):

            # s = abs(x1-x2) * abs(y1-y2)
            # if s == 0:
            #     continue

            # min_x = min(x1, x2)
            # max_x = max(x1, x2)
            # min_y = min(y1, y2)
            # max_y = max(y1, y2)

            contains_count = 0
            for x3, y3 in zip(x, y):
                if min_x <= x3 <= max_x and min_y <= y3 <= max_y:
                    contains_count += 1
            if contains_count >= K:
                s = (max_x - min_x) * (max_y - min_y)
                ans = min(ans, s)

    print(ans)


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

h,w,m=map(int,input().split())
H=[0]*(3*10**5+1)
W=[0]*(3*10**5+1)
M=[]
for i in range(m):
    h,w=map(int,input().split())
    M.append([h,w])
    H[h]+=1
    W[w]+=1

p=max(H)
q=max(W)

X=set([i for i in range(3*10**5+1) if H[i]==p])
Y=set([i for i in range(3*10**5+1) if W[i]==q])

Z=[[M[i][0],M[i][1]] for i in range(m) if M[i][0] in X or M[i][1] in Y ]

cnt=1
flag=True
for x in X:
    if flag:
        for y in Y:
            if not [x,y] in Z:
                cnt=0
                flag=False
                break

print(p+q-cnt)

### FIXED CODE ###

h,w,m=map(int,input().split())
H=[0]*(3*10**5+1)
W=[0]*(3*10**5+1)
M=[]
for i in range(m):
    h,w=map(int,input().split())
    M.append([h,w])
    H[h]+=1
    W[w]+=1

p=max(H)
q=max(W)

X=set([i for i in range(3*10**5+1) if H[i]==p])
Y=set([i for i in range(3*10**5+1) if W[i]==q])

cnt=0
for i in range(m):
    if M[i][0] in X and M[i][1] in Y:
        cnt+=1

if cnt==len(X)*len(Y):
    print(p+q-1)
else:
    print(p+q)
### BUGGY CODE ###

N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(M)]

group = [set([i]) for i in range(N)]
syozoku = [i for i in range(N)]


for a,b in AB:
  a -= 1
  b -= 1
  group[syozoku[a]] = group[syozoku[a]] | group[syozoku[b]]
  x = group[syozoku[b]].copy()
  if syozoku[a]!=syozoku[b]:
  	group[syozoku[b]] = set([])
  for i in x:
    syozoku[i] = syozoku[a]
  
ans = 0
for i in range(N):
  ans = max(len(group[i]),ans)
  
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(M)]
from collections import deque
friends = [deque() for _ in range(N)]
ans = 0

for a,b in AB:
  a -= 1
  b -= 1
  friends[a].append(b)
  friends[b].append(a)
  
flag = [False] * N
for i in range(N):
  if flag[i]:
    continue
  else:
    x = friends[i]
    tmp = 1
    flag[i] = True
    while len(x)!=0:
      y = x.pop()
      if flag[y]:
        continue
      else:
        tmp += 1
        for j in friends[y]:
          x.append(j)
        flag[y] = True
    ans = max(tmp,ans)
    
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
nl = {}
cl = {}
for num in l:
  if num in nl:
    nl[num] = nl[num] + 1
  else:
    nl[num] = 1
for n in nl:
  cnt = 0
  for m in nl:
    if n == m:
      if nl[m]-1 > 1:
        cnt += (nl[m]-1) * (nl[m]-2) / 2
    else:
      if nl[m] > 1:
        cnt += nl[m] * (nl[m]-1) / 2
  cl[n] = int(cnt)
for i in l:
  print(cl[i])

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
nl = {}
cal = {}
kal = {}
cl = {}
all = 0
for num in l:
  if num in nl:
    nl[num] = nl[num] + 1
  else:
    nl[num] = 1
for n in nl:
  if nl[n] > 1:
    cal[n] = nl[n] * (nl[n]-1) / 2
  else:
    cal[n] = 0
  if nl[n]-1 > 1:
    kal[n] = (nl[n]-1) * (nl[n]-2) / 2
  else:
    kal[n] = 0
  all += cal[n]
for n in nl:
  cl[n] = int(all - cal[n] + kal[n])
for i in l:
  print(cl[i])
### BUGGY CODE ###

N=int(input())
S=[]
for i in range(N):
    A=input()
    if A not in S:
        S.append(A)
print(len(S))

### FIXED CODE ###

N=int(input())
S=[]
for i in range(N):
    A=input()
    S.append(A)
print(len(set(S)))
### BUGGY CODE ###

s = input()
q = int(input())

def addflont(s,c):
    return c+s
def addback(s,c):
    return s+c

reverse = 0

for i in range(q):
    t = [str(i) for i in input().split()]

    if t[0]=="1":
        reverse += 1
    if t[0]=="2":
        if t[1]=="1":
            if reverse%2==0:
                s = addflont(s,t[2])
            else:
                s = addback(s,t[2])
        elif t[1]=="2":
            if reverse%2==0:
                s = addback(s,t[2])
            else:
                s = addflont(s,t[2])

if reverse%2==1:
    print(s[::-1])
else:
    print(s)


### FIXED CODE ###



s = input()
q = int(input())

def addflont(s,c):
    text = "".join([c,s])
    return text
def addback(s,c):
    text = "".join([s,c])
    return text

reverse = 0
r = "";u = ""
for i in range(q):
    t = input()
    if t[0]=="1":
        reverse = reverse^1
    if t[0]=="2":
        if t[2]=="1":
            if reverse==0:
                r = addflont(r,t[4])
            else:
                u = addback(u,t[4])
        elif t[2]=="2":
            if reverse==0:
                u = addback(u,t[4])
            else:
                r = addflont(r,t[4])

s = r + s + u
if reverse==1:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

from heapq import *
class PriorityQueue(object):
    def __init__(self):
        self.queue = []
    def push(self, value):
        heappush(self.queue, value)
    def pop(self):
        return heappop(self.queue)
    def empty(self):
        return len(self.queue) == 0
    def size(self):
        return len(self)

from numpy import array,inf


def djikstra(s):
    que = PriorityQueue()
    d = [inf]*V
    d[s] = 0
    que.push((0,s))
    while(not que.empty()):
        p = que.pop()
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                que.push((d[e[0]],e[0]))
    return d


n,m,s,t = map(int,input().split())
V = n
Ga = [[]]*n
Gb = [[]]*n
for i in range(n):
    Ga[i]=[]
    Gb[i]=[]
for i in range(m):
    u,v,a,b = map(int,input().split())
    Ga[u-1].append((v-1,a))
    Ga[v-1].append((u-1,a))
    Gb[u-1].append((v-1,b))
    Gb[v-1].append((u-1,b))

G = Ga
S = djikstra(s-1)
G = Gb
T = djikstra(t-1)

M = array(S)+array(T)

for i in range(n):
    print(10**15-min(M[i:]))


### FIXED CODE ###

from heapq import *
from numpy import array,inf


def djikstra(G,s):
    que = []
    d = [inf]*V
    d[s] = 0
    visited = [False] * V
    heappush(que,(0,s))
    while(len(que)!=0):
        p = heappop(que)
        v = p[1]
        if visited[v]:
            continue
        visited[v] = True
        for i in range(len(G[v])):
            e = G[v][i]
            if visited[e[0]]:
                continue
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que,(d[e[0]],e[0]))
    return d


n,m,s,t = map(int,input().split())
V = n
Ga = [[] for i in range(n)]
Gb = [[] for i in range(n)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    Ga[u-1].append((v-1,a))
    Ga[v-1].append((u-1,a))
    Gb[u-1].append((v-1,b))
    Gb[v-1].append((u-1,b))

S = djikstra(Ga,s-1)

T = djikstra(Gb,t-1)

M = 10**15-(array(S)+array(T))
ans = [0]*n
ans[n-1] = M[n-1]
for i in range(n-2,-1,-1):
    ans[i] = max(ans[i+1],M[i])

for i in range(n):
    print(ans[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())
V = sum(v)
dp = [[float("inf")] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
	for j in range(V + 1):
		if j - v[i] >= 0:
			dp[i + 1][j] = dp[i][j - v[i]] + w[i]
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
ans = 0
for j in range(V + 1):
	if dp[N][j] <= W:
		ans = j
print(ans)


### FIXED CODE ###

N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())

V = sum(v)
dp = [[float("inf")] * (V + 1) for _ in range(N + 1)]
"""
for j in range(V + 1):
	dp[0][j] = 0
"""
dp[0][0] = 0
# dp[i][j]:i番目までの品物から価値がj以上になるよう選んだときの重さの総和の最小値
for i in range(N):
	for j in range(V + 1):
		# i+1番目を選ぶ場合
		if j - v[i] >= 0:
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i])
		# i+1番目を選ばない場合
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

# print(dp)

# dp[N][j]がW以下であるようなjの最大値が答えになる
ans = 0
for j in range(V + 1):
	if dp[N][j] <= W:
		ans = j

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

import math

N = int(input())
A = []
for i in range(2,int(math.sqrt(N))+1):
    if N%i == 0:
        for j in range(1,N//2+1):
            if N == i * j:
                A.append(i + j - 2)
if not A:
    print(N-1)
else:
    print(min(A))

### FIXED CODE ###

import math

N = int(input())
A = []
for i in range(2,int(math.sqrt(N))+1):
    if N%i == 0:
        A.append(i + (N//i) - 2)
if not A:
    print(N-1)
else:
    print(min(A))
### BUGGY CODE ###

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    A = tuple(map(int, input().split()))

    DP = [[[0] * 3 for _ in range(S + 1)] for _ in range(N + 1)]
    DP[0][0][0] = 1

    for i in range(N):
        DP[i + 1][0][0] = DP[i][0][0] 
        DP[i + 1][0][1] = DP[i][0][0] + DP[i][0][1]
        a = A[i]
        if a > S:
            for j in range(1, S + 1):
                DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1]) % MOD #以前から合計jになっている場合のみOK
        else:
            for j in range(1, a):
                DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1]) % MOD #以前から合計jになっている場合のみOK
            for j in range(a, S + 1):
                DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1] + DP[i][j - a][0] + DP[i][j - a][1]) % MOD

        DP[i + 1][S][2] = (DP[i][S][1] + DP[i][S][2])
        if a <= S:
            DP[i + 1][S][2] += DP[i][S - a][0] + DP[i][S - a][1]
        DP[i + 1][S][2] %= MOD

    print (DP[N][S][2])

    # for i in range(N + 1):
    #     print (DP[i])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    A = tuple(map(int, input().split()))

    DP0 = [[0] * (S + 1) for _ in range(N + 1)]
    DP1 = [[0] * (S + 1) for _ in range(N + 1)]
    DP2 = [[0] * (S + 1) for _ in range(N + 1)]

    DP0[0][0] = 1

    for i in range(N):
        DP0[i + 1][0] = DP0[i][0] 
        DP1[i + 1][0] = DP0[i][0] + DP1[i][0]
        a = A[i]
        if a > S:
            for j in range(1, S + 1):
                DP1[i + 1][j] = DP1[i][j] #以前から合計jになっている場合のみOK
        else:
            for j in range(1, a):
                DP1[i + 1][j] = DP1[i][j] #以前から合計jになっている場合のみOK
            for j in range(a, S + 1):
                DP1[i + 1][j] = (DP1[i][j] + DP0[i][j - a] + DP1[i][j - a]) % MOD
                # DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1] + DP[i + 1][j - a][1]) % MOD

        DP2[i + 1][S] = (DP1[i][S] + DP2[i][S])
        if a <= S:
            DP2[i + 1][S] += DP0[i][S - a] + DP1[i][S - a]
        DP2[i + 1][S] %= MOD

    print (DP2[N][S])

    # for i in range(N + 1):
    #     print (DP[i])

if __name__ == '__main__':
    main()