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

N = int(input())
S = list(input() for i in range(N))
max = 0

for i in S:
    if S.count(i) > max:
        max = S.count(i)
        List = [i]
    elif S.count(i) == max:
        List.append(i)

set = set(List)
List2 = list(set)
List2.sort()

for i in List2:
    print(i)

### FIXED CODE ###

import collections

N = int(input())
S = list(input() for i in range(N))
dict = {}

for l in S:
        if l in dict:
            dict[l] += 1;
        else:
            dict[l] = 1;
            
max = max(dict.values())

max_k_list = [kv[0] for kv in dict.items() if kv[1] == max]

max_k_list.sort()

for i in max_k_list:
    print(i)
### BUGGY CODE ###

import itertools

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

for i,j,k in itertools.combinations(l, 3):
  if i < j+k and j < i+k and k< j+i:
    count += 1
    
print(count)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
 
import bisect
 
ans=0
l.sort()
 
for i in range(n):
    a=l[i]#一番短い棒を確定
    for j in range(i+1,n):
        b=l[j]#二番目に短い棒を確定
        ind=bisect.bisect_left(l,a+b)#二辺の和と同じだったら耐えないので，left
        ans+=max(0,ind-(j+1))#三角形の成立条件と，一番長い棒であることを考える

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

[N,K] = [int(s) for s in input().rstrip().split(' ')]
L_A = [int(s) for s in input().rstrip().split(' ')]
if N < K:
  print("error")
elif N == K:
  print((sum(L_A) + N) / 2)
else:
  a = N - K
  p = 0
  for i in range(a + 1):
    x = 0
    for j in range(K):
      x += L_A[i + j]
    p = max(p,x)
  print((p + K) / 2)

### FIXED CODE ###

[N,K] = [int(s) for s in input().rstrip().split(' ')]
L_A = [int(s) for s in input().rstrip().split(' ')]
if N < K:
  print("error")
elif N == K:
  print((sum(L_A) + N) / 2)
else:
  a = N - K
  p = 0
  for i in range(K):
    p += L_A[i]
  q = p
  for j in range(N-K):
    q += L_A[j+K]-L_A[j]
    p = max(p,q)
  print((p + K) / 2)
### BUGGY CODE ###

import collections
_=int(input())
l = list(map(int, input().split()))
c = collections.Counter(l)
M={}
for i,v in c.items():
    M[i] =  v*(v-1)/2

for k in l:
    M_ = M.copy()
    M_[k] =  M_[k]*(c[k]-2)/c[k]
    print(int(sum(M_.values())))


### FIXED CODE ###

import collections
_ = int(input())
l = list(map(int, input().split()))
c = collections.Counter(l)
M=0
for v in c.values():
    if v>1:
        M +=  v*(v-1)/2

for k in l:
    print(int(M-c[k]+1))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, W = [int(x) for x in input().split()]
wv = []
for _ in range(N):
    wv.append([int(x) for x in input().split()])

dp = [[0] * (W + 1) for _ in range(N + 1)]

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

print(dp[N][W])

### FIXED CODE ###

N,W=map(int,input().split())
A=[]
for _ in range(N):
    B=list(map(int,input().split()))
    A.append(B)
dp=[]
for _ in range(N):
    dp.append([0]*(W+1))
for j in range(W+1):
    if j>=A[0][0]:
        dp[0][j]=A[0][1]
for i in range(0,N-1):
    for w in range(W+1):
        if w>=A[i+1][0]:
            dp[i+1][w]=max(dp[i][w-A[i+1][0]]+A[i+1][1],dp[i][w])
        else:
            dp[i+1][w]=dp[i][w]
print(dp[N-1][W])
### BUGGY CODE ###

X = int(input())
ans = pow(10, 9)
for t in range(X + 1):
  if t*(t+1) / 2 >= X and t < ans:
    ans = t
print(ans)

### FIXED CODE ###

X = int(input())
ans = pow(10, 9)
for t in range(X + 1):
  if t*(t+1) / 2 >= X and t < ans:
    ans = t
    break
print(ans)
### BUGGY CODE ###

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

gate = []

for i in range(M):
    l, r = map(int, input().split())
    tmp = []
    for j in range(l, r + 1):
        tmp.append(j)
    gate.append(tmp)

gate_sum = set(gate[0])

for i in gate:
    gate_sum = gate_sum & set(i)

print(len(gate_sum))

### FIXED CODE ###

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

gate = []

l, r = map(int, input().split())


for i in range(M-1):
    tmpl, tmpr = map(int, input().split())
    if l < tmpl:
        l = tmpl
    if tmpr < r:
        r = tmpr


if r - l < 0:
    print(0)
else:
    print(r - l + 1)
### BUGGY CODE ###

def get_point(machine_hand, R, S, P):
    """ 筐体がmachine_handを出した場合，勝った時に得られるポイント
    """
    if machine_hand == 'r':
        return P
    elif machine_hand == 's':
        return R
    elif machine_hand == 'p':
        return S



def main():
    N, K = list(map(int, input().split()))
    R, S, P = list(map(int, input().split()))
    T = input()

    points = []
    used_trials = []
    for i in range(0, len(T)):
        if i < K:
            points.append(get_point(T[i], R, S, P))            
            used_trials.append(i)
        else:
            if T[i] == T[i - K] and i - K in used_trials:
                points.append(0)
            else:
                points.append(get_point(T[i], R, S, P))
                used_trials.append(i)
        
    print(sum(points))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def get_point(machine_hand, R, S, P):
    """ 筐体がmachine_handを出した場合，勝った時に得られるポイント
    """
    if machine_hand == 'r':
        return P
    elif machine_hand == 's':
        return R
    elif machine_hand == 'p':
        return S



def main():
    N, K = list(map(int, input().split()))
    R, S, P = list(map(int, input().split()))
    T = input()

    points = 0
    used_trials = set()
    for i in range(0, len(T)):
        if i < K:
            
            points += get_point(T[i], R, S, P)
            used_trials.add(i)
        else:
            if T[i] == T[i - K] and i - K in used_trials:
                continue
            else:
                # points.append(get_point(T[i], R, S, P))
                points += get_point(T[i], R, S, P)
                used_trials.add(i)
        
    print(points)


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

class UnionFind():
	def __init__(self,size):
		self.table = [-1 for _ in range(size)]

	def find(self,x):
		while self.table[x] >= 0:
			x = self.table[x]
		return x

	def unite(self,x,y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] != self.table[s2]:
				if self.table[s1] < self.table[s2]:
					self.table[s2] = s1
				else:
					self.table[s1] = s2
			else:
				self.table[s1] += -1
				self.table[s2] = s1
		return

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


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

for i in range(M):
	a, b = map(int,input().split())
	if a == 1 or a == N or b == 1 or b == N:
		edges[a-1] += [b-1]
		edges[b-1] += [a-1]

uf = UnionFind(N)

for u in edges[0]:
	if N-1 not in edges[0]:
		uf.unite(0,u)

for v in edges[N-1]:
	if 0 not in edges[N-1]:
		uf.unite(N-1,v)

print("POSSIBLE" if uf.same(0,N-1) == True else "IMPOSSIBLE")

### FIXED CODE ###

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

from1 = []
gotoN = []

for i in range(M):
	a, b = map(int,input().split())
	if a == 1:
		from1.append(b)
	if b == N:
		gotoN.append(a)

res = set(from1) & set(gotoN)

print("POSSIBLE" if len(res) > 0 else "IMPOSSIBLE")
### BUGGY CODE ###

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

i=2
c=0
ans=1
while(True):
    if(P%i==0):
        P=P//i
        c+=1
        if(c%N==0):
            ans*=i
    else:
        break
c=0
i=3 
while(True):
    if(P%i==0):
        P=P//i
        c+=1
        if(c%N==0):
            ans*=i
    else:
        i+=2
        c=0
    
    if((P<i**N)&(c==0)):
        break
print(ans)
    

    

### FIXED CODE ###

import collections

n,p=map(int,input().split())

a=[]
while p % 2 == 0:
  p //= 2
  a.append(2)
f = 3
while f * f <= p:
  if p % f == 0:
    a.append(f)
    p //= f
  else:
    f += 2
if p != 1:
  a.append(p)

dct=collections.Counter(a)

ans=1

li=dct.items()

for tt in li:
  if tt[1]//n>=1:
    ans*=tt[0]**(tt[1]//n)
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())

dic = {}
for i in range(n):
    a, b = map(int, input().split())
    if a >= m+1:
        continue
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
# print(dic)

ans = 0
l = []
for j in range(1, m+1):
    if j in dic.keys():
        l += dic[j]
        l.sort()
    #print(l)
    if l:
        ans += l[-1]
        l.pop()

print(ans)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())

dic = {}
for i in range(n):
    a, b = map(int, input().split())
    if a >= m+1:
        continue
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]

ans = 0
l = []
heapq.heapify(l)
for j in range(1, m+1):
    if j in dic.keys():
        for x in dic[j]:
            heapq.heappush(l, -x)
    if l:
        ans += -l[0]
        heapq.heappop(l)

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

k, s = map(int, input().split())
res = 0

for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if (x + y + z) == s:
        res += 1
        
print(res)

### FIXED CODE ###

k, s = map(int, input().split())
res = 0

for x in range(k+1):
  for y in range(k+1):
    z = s - (x + y)
    if z >= 0 and z <= k:
      res += 1
        
print(res)
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
mx = 1E18
ans = 1 ;
for i in range(0, n) :
    ans *= x[i]
if ans > mx :
    print(-1)
else :
    print(ans)

### FIXED CODE ###

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

if 0 in x :
    print(0)
else :
    ans = 1
    con = True
    for i in range(0, n):
        ans *= x[i]
        if ans > 1000000000000000000:
            print(-1)
            con = False
            break
    if con : print(ans)
### BUGGY CODE ###

s = input()
t = input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
# 最長の文字数を求める
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1], dp[i + 1][j])

# print(dp[-1][-1]) # 最長文字数
i, j = len(s), len(t)

ans = []
while i > 0 and j > 0:
    if s[i - 1] == t[j - 1] and dp[i][j] == dp[i - 1][j - 1] + 1:
        ans.append(s[i - 1])
        i -= 1
        j -= 1
    else:
        if dp[i - 1][j] == dp[i][j]:
            i -= 1
        else:
            j -= 1
print(*reversed(ans), sep='')


### FIXED CODE ###

s = input()
t = input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
# 最長の文字数を求める
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1], dp[i + 1][j])

# print(dp[-1][-1]) # 最長文字数
i, j = len(s), len(t)

ans = []
while i > 0 and j > 0:
    if s[i - 1] == t[j - 1] and dp[i][j] == dp[i - 1][j - 1] + 1:
        ans.append(s[i - 1])
        i -= 1
        j -= 1
    else:
        if dp[i - 1][j] == dp[i][j]:
            i -= 1
        else:
            j -= 1
print(*reversed(ans), sep='')
### BUGGY CODE ###

N, M = map(int, input().strip().split())

for i in range(M//N,-1,-1):
    if M%i==0:
        print(i)
        break

### FIXED CODE ###

import math
N, M = map(int, input().strip().split())
st= min(M//N,int(math.sqrt(M)))
cand=0
if M//N <= int(math.sqrt(M)):
    for i in range(M//N,0,-1):
        if M%i==0:
            print(i)
            break
else:
    for i in range(1,int(math.sqrt(M)),1):
        if M%i==0:
            if M//N >= i:
                cand=max(cand,i)
            if M//N >= M//i:
                cand=max(cand,M//i)
    print(cand)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
MOD = 998244353

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

ans = 0
dp = [0]*(S+1)
for i in range(N):
    dp[0] += 1      # Lがiからを足す
    next_dp = [0]*(S+1)
    for j in range(S+1):
        next_dp[j] += dp[j]             # A[i]を選ばない
        next_dp[j] %= MOD
        if j+A[i]<=S:
            next_dp[j+A[i]] += dp[j]    # A[i]を選ぶ
            next_dp[j] %= MOD
    dp = next_dp
    ans += dp[S]    # Rがiまでを足す
    ans %= MOD

print(ans)


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
MOD = 998244353

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

ans = 0
dp = [0]*(S+1)
for i in range(N):
    dp[0] += 1      # Lがiからを足す
    next_dp = [0]*(S+1)
    for j in range(S+1):
        next_dp[j] += dp[j]             # A[i]を選ばない
        next_dp[j] %= MOD
        if j+A[i]<=S:
            next_dp[j+A[i]] += dp[j]    # A[i]を選ぶ
            next_dp[j] %= MOD
    dp = next_dp
    ans += dp[S]    # Rがiまでを足す
    ans %= MOD

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

a,b,c,d=map(int, input().split())
maximum = -1000000000000000000
for i in range(a,b+1):
    for j in range(c,d+1):
        if i*j > maximum:
            maximum = i*j
print(maximum)

### FIXED CODE ###

a,b,c,d=map(int, input().split())
maximum_list=(a*c,a*d,b*c,b*d)
print(max(maximum_list))
### BUGGY CODE ###

s = input()
n = len(s)
mod = 2019
dp = [0 for i in range(n)]
for i,c in enumerate(s):
    dp[i] = int(c) % mod

cum = [0]*n
cum[0] = dp[0]
cum[n-1] = int(s[-1]) % mod
d = 10
for i in range(0, n-1)[::-1]:
    a = int(s[i])* d % mod
    cum[i] = (cum[i+1]+a) % mod
    d *= 10
cnt = [0]*mod

ans = 0
for i in cum[::-1]:
    ans += cnt[i]
    cnt[i] += 1
    if i == 0:
        ans += 1
print(ans)

### FIXED CODE ###

s = input()
n = len(s)
mod = 2019

cum = [0]*n
cum[n-1] = int(s[-1]) % mod
d = [1]*n
for i in range(n-1)[::-1]:
    d[i] = d[i+1]*10%mod

for i in range(0, n-1)[::-1]:
    a = int(s[i]) * d[i] % mod
    cum[i] = (cum[i+1]+a) % mod
cnt = [0]*mod

ans = 0
for i in cum[::-1]:
    ans += cnt[i]
    cnt[i] += 1
    if i == 0:
        ans += 1
print(ans)
### BUGGY CODE ###

from collections import defaultdict
def main():
    def f(n):
        if n == 0:
            return 0
        if d[n] != 0:
            return d[n]
        d[n] = f(n % sum(list(map(int, bin(n)[2:])))) + 1
    def rev(i):
        nonlocal c, X, m
        if X[i] == '0':
            c += 1
            m += 1 << (n - i - 1)
        else:
            c -= 1
            m -= 1 << (n - i - 1)
    def res(i):
        nonlocal c, X, m
        if X[i] == '0':
            c -= 1
            m -= 1 << (n - i - 1)
        else:
            c += 1
            m += 1 << (n - i - 1)

    n = int(input())
    X = list(input())
    d = defaultdict(int)
    d[0] = 0
    printl = lambda x, y: print(d[x % y] + 1 if x != 0 else 0)
    for i in range(1, n):
        f(i)
    c = sum(list(map(int, X)))
    m = int(''.join(X), 2)
    for i in range(n):
        rev(i)
        printl(m, c)
        res(i)





if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    def f(n):
        if n == 0: return 0
        return f(n % bin(n).count('1')) + 1
    n = int(input())
    X = list(input())
    c = sum(list(map(int, X)))
    m = int(''.join(X), 2)
    mp, mm = m % (c + 1), m % (c - 1) if c - 1 != 0 else 0
    jp, jm = 1, 1
    ans = [0] * n
    for i in range(n - 1, -1, -1):
        if X[i] == '0':
            mod = c + 1
            ans[i] = f((mp + jp) % mod) + 1
        else:
            ans[i] = f((mm - jm + mod) % mod) + 1 if (mod := c - 1) != 0 else 0
        jp, jm = (jp << 1) % (c + 1), (jm << 1) % (c - 1) if c - 1 != 0 else 0
    [print(a) for a in ans]
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def solve():
    from collections import defaultdict
    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.par = [-1] * n

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

        def unite(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.par[x] > self.par[y]:
                x, y = y, x

            self.par[x] += self.par[y]
            self.par[y] = x

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

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

    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    mp = defaultdict(int)
    uf = UnionFind(n)

    for i in range(n):
        uf.unite(i, p[i] - 1)

    for i in range(n):
        mp[uf.find(i)] += c[i]

    ans = -10 ** 14
    for i in range(n):
        roop = uf.size(i)
        times = (k - 1) // roop if mp[uf.find(i)] > 0 else 0
        over = max(min(roop, k - roop * times), 1)
        tmp = 0
        s = -10 ** 10
        idx = i
        for j in range(over):
            tmp += c[idx]
            s = max(s, tmp)
            idx = p[idx] - 1
        s += times * mp[uf.find(i)]
        ans = max(ans, s)
    print(ans)


solve()


### FIXED CODE ###

def solve():
    from collections import defaultdict
    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.par = [-1] * n

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

        def unite(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.par[x] > self.par[y]:
                x, y = y, x

            self.par[x] += self.par[y]
            self.par[y] = x

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

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

    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    mp = defaultdict(int)
    uf = UnionFind(n)

    for i in range(n):
        uf.unite(i, p[i] - 1)

    for i in range(n):
        mp[uf.find(i)] += c[i]

    ans = -10 ** 14
    for i in range(n):
        roop = uf.size(i)
        times = (k - 1) // roop if mp[uf.find(i)] > 0 else 0
        over = max(min(roop, k - roop * times), 1)
        tmp = 0
        s = -10 ** 10
        idx = i
        for j in range(over):
            tmp += c[idx]
            s = max(s, tmp)
            idx = p[idx] - 1
        s += times * mp[uf.find(i)]
        ans = max(ans, s)
    print(ans)


solve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    ls = [[int(_) for _ in input().split()] for _ in range(m)]
    
    dp = [[] for _ in range(n)] 

    for i in range(m):
        dp[ls[i][0] - 1].append(ls[i][1])
    
    for j in range(n):
        dp[j].sort()

    for k in range(m):
        th = dp[ls[k][0] - 1].index(ls[k][1]) + 1
        print(str(ls[k][0]).zfill(6) + str(th).zfill(6))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())

    dp = [[] for _ in range(n)]
    ans = [0] * m

    for i in range(m):
        p, y = map(int, input().split())
        dp[p - 1].append((y, i))
    
    for j, k in enumerate(dp):
        k.sort()    
        for l, (s, t) in enumerate(k):
            ans[t] = str(j + 1).zfill(6) + str(l + 1).zfill(6)
    
    print(*ans, sep = "\n")


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

import sys

N, K = map(int, input().split())
H = list(map(int, sys.stdin.readline().rsplit()))

dp = [10 ** 9] * (N + K)
dp[0] = 0

for i in range(N):
    for k in range(1, K + 1):
        if i + k < N:
            dp[i + k] = min(
                dp[i + k],
                dp[i] + abs(H[i] - H[i + k])
            )

print(dp[N - 1])


### FIXED CODE ###

import sys

N, K = map(int, input().split())
H = list(map(int, sys.stdin.readline().rsplit()))

dp = [10 ** 9] * (N + K)
dp[0] = 0

for i in range(N):
    for k in range(1, K + 1):
        if i + k < N:
            dp[i + k] = min(
                dp[i + k],
                dp[i] + abs(H[i] - H[i + k])
            )

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

class WarshallFroyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float('inf')] * N for _ in range(N)]

    def add(self, u, v, c, directed=False):
        """
        Valid only for '0-indexed' graphs!
        add an edge from u to v with cost d
        """
        if directed == False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self, DetectNegativeCycle=False):
        """
        Change self.d to self.d[i][j] = (minimal cost from i to j)
        If self.d[i][j] < 0, this graph has negative loops
        """
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        if DetectNegativeCycle == True:
            hasNegativeCycle = False
            for i in range(self.N):
                if self.d[i][i] < 0:
                    hasNegativeCycle = True
                    break
        for i in range(self.N):
            self.d[i][i] = 0
        if DetectNegativeCycle == True:
            return hasNegativeCycle, self.d
        else:
            return self.d



N, M, L = map(int, input().split())
graph = WarshallFroyd(N)
for _ in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, c)
d = graph.WarshallFloyd_search()
#print('distance={}'.format(d))


graph2 = WarshallFroyd(N)
for a in range(N - 1):
    for b in range(a+1, N):
        if d[a][b] <= L:
            graph2.add(a, b, 1)
times = graph2.WarshallFloyd_search()
#print('times={}'.format(times))


Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    if times[s-1][t-1] != float('inf'):
        print(times[s-1][t-1] - 1)
    else:
        print(-1)


### FIXED CODE ###

inf = 10 ** 15

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

for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
#print('distance={}'.format(dp))


dp2 = [[inf] * N for _ in range(N)]
for a in range(N - 1):
    for b in range(a+1, N):
        if dp[a][b] <= L:
            dp2[a][b] = 1
            dp2[b][a] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp2[i][j] = min(dp2[i][j], dp2[i][k] + dp2[k][j])
#print('times={}'.format(dp2))


Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    cost = dp2[s-1][t-1]
    if cost != inf:
        print(cost - 1)
    else:
        print(-1)
### BUGGY CODE ###

N,W=map(int,input().split())
A = [list(map(int, input().split())) for i in range(N)]



dp = [[0 for i in range(W+1)] for j in range(N+1)]


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

### FIXED CODE ###

N,W=map(int,input().split())
A = [list(map(int, input().split())) for i in range(N)]



max_sum = sum([i[1] for i in A])

max_value=10**10
dp = [[max_value for i in range(max_sum+1) ] for j in range(N+1)]
dp[0][0]=0

for i in range(N):
    for v in range(max_sum+1):
        if v>=A[i][1]:
            dp[i+1][v] = min([dp[i][v-A[i][1]]+A[i][0], dp[i][v]])

        else:
            dp[i+1][v] = dp[i][v]

#ここでindexは価値と同値、複数あることを考慮して反転後indexで最も価値のある個所を取得
# try:
#     print(max_sum-dp[N][::-1].index(W))
# except:
#     print(max_sum-dp[N][::-1].index(W))
for i,w in enumerate(dp[N][::-1]):
    if w <=W:
        print(max_sum-i)
        break
#     print(int(dp[N][W]))