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

import sys
from scipy.sparse.csgraph import dijkstra

N = int(sys.stdin.buffer.readline())

graph = [[0]*N for _ in range(N)]

for _ in range(N-1):
    a, b, c = map(int, sys.stdin.buffer.readline().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

Q, K = map(int, sys.stdin.buffer.readline().split())
dist_K = dijkstra(graph, indices = K-1)

ans = []
for _ in range(Q):
    x, y = map(int, sys.stdin.buffer.readline().split())
    ans.append(int(dist_K[x-1] + dist_K[y-1]))

print("\n".join(map(str, ans)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)

N = int(sys.stdin.buffer.readline())

graph = [[]*N for _ in range(N)]

for _ in range(N-1):
    a, b, c = map(int, sys.stdin.buffer.readline().split())
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))

Q, K = map(int, sys.stdin.buffer.readline().split())
dist_K = [-1]*N

def cal_dist_K(u = K-1, current_dist = 0):
    dist_K[u] = current_dist
    for v,c in graph[u]:
        if dist_K[v] == -1:
            cal_dist_K(v, current_dist + c)

cal_dist_K()

ans = []
for _ in range(Q):
    x, y = map(int, sys.stdin.buffer.readline().split())
    ans.append(int(dist_K[x-1] + dist_K[y-1]))

print("\n".join(map(str, ans)))
### BUGGY CODE ###

import collections

def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod
    
n = int(input())
li = list(map(int,input().split()))

for i in range(n):
    li_a = li.copy()
    del li_a[i]
    c = collections.Counter(li_a)
    s = list(set(li_a))
    ans = 0
    # print(c)
    # print(c[s[1]])
    # print(s)
    
    for j in range(len(s)):
        if c[s[j]] <= 1:
            continue
        ans += combination(c[s[j]], 2)
        
    print(ans)

### FIXED CODE ###

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

ans_li = [0]*(n+10)

for i in li:
    ans_li[i] += 1
    
result = 0    
for i in ans_li:
    result += (i * (i-1)) // 2
    
for i in li:
    ans = result
    ans += ((ans_li[i] - 1) * (ans_li[i] - 2)) // 2- (ans_li[i] * (ans_li[i] - 1)) // 2
    print(ans)
### BUGGY CODE ###

x = int(input())
a = 0
b = 0
b2 = 0
judge = 0

while a**5 - b**5 < 10**9:
    while a**5 - b**5 > 0:
        if a**5 - b**5  == x:
            judge = 1
            print(a ,b)
            break
        b += 1
    else:
        a += 1
        continue
    break

if judge == 0:
    a = 0
    while a**5 - b2**5 < 10**9:
        while a**5 - b2**5 > 0:
            if a**5 - b2**5  == x:
                print(a ,b2)
                break
            b2 -= 1
        else:
            a += 1
            continue
        break





### FIXED CODE ###

x = int(input())
a = 0

while True:
    b = 0
    b2 = 0
    while a**5 - b**5 > 0 or a**5 - b2**5 < 10**9:
        if a**5 - b**5  == x:
            print(a ,b)
            break
        b += 1
        if a**5 - b2**5 == x:
            print(a ,b2)
            break
        b2 -= 1
    else:
        a += 1
        continue
    break
### BUGGY CODE ###

import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    R, C, K = read_values()
    V = [0] * (R * C)
    for _ in range(K):
        r, c, v = read_values()
        r -= 1
        c -= 1
        V[r * C + c] = v
    
    dp = [[0, 0, 0, 0] for _ in range(R * C)]
    for i in range(R * C):
        r = i // C
        c = i % C
        if c + 1 < C:
            # not take
            for k in range(4):
                dp[i + 1][k] = max(dp[i + 1][k], dp[i][k])

            # take 
            for k in range(3):
                dp[i + 1][k + 1] = max(dp[i + 1][k + 1], dp[i][k] + V[i])

        # next r
        if r + 1 < R:
            for k in range(4):
                dp[i + C][0] = max(dp[i + C][0], dp[i][k] + (V[i] if k < 3 else 0))

    print(max(k + (V[-1] if i  < 3 else 0) for i, k in enumerate(dp[-1])))


if __name__ == "__main__":
    main()



### FIXED CODE ###

import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    R, C, K = read_values()
    V = [0] * (R * C)
    for _ in range(K):
        r, c, v = read_values()
        r -= 1
        c -= 1
        V[r * C + c] = v
    
    dp = [0 for _ in range(R * C * 4)]
    for i in range(R * C):
        r = i // C
        c = i % C
        if c + 1 < C:
            # not take
            for k in range(4):
                dp[4 * (i + 1) + k] = max(dp[4 * (i + 1) + k], dp[4 * i + k])

            # take 
            for k in range(3):
                dp[4 * (i + 1) + k + 1] = max(dp[4 * (i + 1) + k + 1], dp[4 * i + k] + V[i])

        # next r
        if r + 1 < R:
            for k in range(4):
                dp[4 * (i + C)] = max(dp[4 * (i + C)], dp[4 * i + k] + (V[i] if k < 3 else 0))

    res = 0
    for k in range(4):
        res = max(res, dp[4 * (R * C - 1) + k] + (V[-1] if k < 3 else 0))

    print(res)


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

N = int(input())
S = input()
num = []

for i in range(N):
    if i == 0:
        East = []
    else:
        East = S[:i]

    if i == N:
        West = []
    else:
        West = S[(i+1):]
    num.append(East.count("W")+West.count("E"))
print(min(num))


### FIXED CODE ###

N = int(input())
S = input()
east = S.count("E")
west = 0
min = east

for i in S:
    if i == "E":
        east -= 1
    else:
        west += 1
    if min > east + west:
        min = east + west

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

import sys,heapq,math,resource
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(resource.RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  resource.setrlimit(resource.RLIMIT_STACK, (256*1024*1024,hard))

def dfs(i,fromup):
    y[i] = fromup + v[i]
    for d in dst[i]:
        dfs(d,y[i])

setrlim()
n,q = inm()
dst = [ [] for i in range(n) ]
for i in range(n-1):
    a,b = inm()
    a -= 1
    b -= 1
    dst[a].append(b)
v = [0]*n
for i in range(q):
    p,x = inm()
    p -= 1
    v[p] += x
y = [0]*n
dfs(0,0)
for i in range(n):
    printn((' ' if i>0 else '') + str(y[i]))
print("")


### FIXED CODE ###

import sys,resource
from collections import deque
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9 + 7

def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(resource.RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  resource.setrlimit(resource.RLIMIT_STACK, (256*1024*1024,hard))

n,q = inm()
dst = [ [] for i in range(n) ]
for i in range(n-1):
    a,b = inm()
    a -= 1
    b -= 1
    dst[a].append(b)
v = [0]*n
for i in range(q):
    p,x = inm()
    p -= 1
    v[p] += x
y = [0]*n

d = deque([])
d.append(0)
while len(d)>0:
    i = d.popleft()
    for j in dst[i]:
        v[j] += v[i]
        d.append(j)

for i in range(n):
    printn((' ' if i>0 else '') + str(v[i]))
print("")
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[False] *(W+2) for _ in range(H+2)]
#queue = []
queue = deque()
for i in range(H):
  line = input()
  for j,ch in enumerate(line):
    if ch == "#":
      mark_matrix[i+1][j+1] = True
      queue.append((i+1,j+1))
for i in range(H+2):
  mark_matrix[i][0] = True
  mark_matrix[i][W+1] = True
for j in range(W+2):
  mark_matrix[0][j] = True
  mark_matrix[H+1][j] = True
  
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))

  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]
#mark_matrix.extend([[True]+[False]*(W)+[True] for _ in range(H)])
mark_matrix.extend([[True]+[x!='.' for x in input()] for _ in range(H)])
mark_matrix[H].append(True)
mark_matrix.append([True]*(W+2))
#queue = []
queue = deque()
for i in range(1,H+1):
  for j in range(1,W+1):
    if mark_matrix[i][j]:
      queue.append((i,j))
#  line = input()
#  for j,ch in enumerate(line):
#    if ch == "#":
#      mark_matrix[i+1][j+1] = True
#      queue.append((i+1,j+1))
#for i in range(1,H+1):
#  mark_matrix[i][0] = True
#  mark_matrix[i][W+1] = True
#for j in range(W+2):
#  mark_matrix[0][j] = True
#  mark_matrix[H+1][j] = True
#print(mark_matrix)
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)
### BUGGY CODE ###

N=int(input())
A=[int(i) for i in input().split()]

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


mat = [1]
divs_set = set()
divs_powers = {}
tmp=[0]*len(A)
for j,a in enumerate(A):
    tmp[j] = factorization(a)
    for div in tmp[j]:
        if div[0] not in divs_set:
            divs_set.add(div[0])
            divs_powers[div[0]] = div[1]
        else:
            if divs_powers[div[0]] < div[1]:
                divs_powers[div[0]] = div[1]

all_dict = []
all_set = []
for i,t in enumerate(tmp):
    each_dict = {}
    each_set = set()
    for tt in t:
        each_dict[tt[0]] = tt[1]
        each_set.add(tt[0])
    all_dict.append(each_dict)
    all_set.append(each_set)



Z = 1
for n in divs_set:
    Z = Z * (n ** divs_powers[n])

B = [1] * N
for i, a in enumerate(A):
    for k in divs_set:
        if k in all_set[i]:
            B[i] = B[i]*(k**(divs_powers[k]-all_dict[i][k]))
        else:
            B[i] = B[i]*(k**divs_powers[k])

print(int(sum(B)) % (10 ** 9 + 7))

### FIXED CODE ###

import math
from collections import defaultdict

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

divisor_primes = defaultdict(int)

def prime_factrizer(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

for a in A:
    factrized_a = prime_factrizer(a)
    for prime in factrized_a:
        divisor_primes[prime[0]] = max(divisor_primes[prime[0]],prime[1])

invs = [1] * (max(A) + 1)
for i in range(2, max(A) + 1):
    invs[i] = mod - invs[mod % i] * (mod//i) % mod

lcm = 1
for key in divisor_primes.keys():
    power = divisor_primes[key]
    div = 1
    for i in range(power):
        div *= key
        div %= mod
    lcm *= div

ans = 0

for a in A:
    ans += invs[a]
    ans %= mod
ans *= lcm
ans %= mod
print(ans)
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

#  f = open('C_input_29.txt')
#  lines = f.readlines()
#  f.close()
#  N, M = map(int, lines[0].split())
#  A = []
#  for line in lines[1:]:
#      A.append(int(line))

N, M = LI()
A = []
for i in range(M):
    A.append(_I())

if M != 0:
    # 連続した壊れた段がある場合は0
    B = [i for i in A]
    B.remove(B[0])
    B.append(10**15+100)
    diffs = [b - a for a, b in zip(A,B)]
    #  print(diffs)

    if any(i == 1 for i in diffs):
        # 隣同士なので0
        print(0)
        exit()
#  print('hoge')
"""
考え方
xにたどり着く通りは、x-1とx-2段目にたどり着く通りの合計
dp
3が障害のとき
1へは1通り
2へは0からと1からの2通り
3へは0通り
4へは2からの2通りと、3からの0通りで2通り
5へは3からの0通りと4からの2通りで2通り
6へは4からの2通りと5からの2通りで4通り
"""
#  dp = {}
dp = [0 for i in range(N+1)]
#  print('fua')
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
#  [dp.update({i: (dp[i-1] + dp[i-2])%mod}) if i not in A else dp.update({i: 0}) for i in range(2, N+1)]
for i in range(2, N+1):
    #  print(i)
    # i段目までの通りを計算する
    if i in A:
        # i段目が障害のときは0になっているので飛ばす
        #  dp[i] = 0
        continue
    
    dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[N] % mod)



### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

mod = 10 ** 9 + 7

def get_nums(n):
    res = [0 for _ in range(n)]
    for i in range(n):
        res[i] = int(input())
    return res


def get_numbers():
    return map(int, input().split())


n, m = get_numbers()
a = set(get_nums(m))

dp = [0 for _ in range(n + 1)]
dp[0] = 1
if 1 not in a:
    dp[1] = 1

for i in range(2, n + 1):
    if i not in a:
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] %= mod

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

n,m = map(int,input().split())
a = []
b = []
l = []
ans = 0
count = 0

for i in range(n):
	a_dash,b_dash = map(int,input().split())
	a.append(a_dash)
	b.append(b_dash)

c = zip(a,b)
c = sorted(c)
a,b = zip(*c)
a = list(a)
b = list(b)
a_length = len(a)

for i in reversed(range(m)):
	for j in range(count,a_length):
		if a[j] + i == m:
			l.append(b[j])
			count += 1
		else:
			break
	if len(l) != 0:
		maximum = max(l)
		ans += maximum
		l.pop(l.index(maximum))

print(ans)


### FIXED CODE ###

import sys
import heapq

s = sys.stdin.readlines()
n,m = map(int,s[0].split())
a = []
b = []
l = []
ans = 0
count = 0

for i in range(1,n+1):
	a_dash,b_dash = map(int,s[i].split())
	a.append(-a_dash)
	b.append(-b_dash)

c = zip(a,b)
c = sorted(c,reverse=True)
a,b = zip(*c)
a_length = len(a)

for i in reversed(range(m)):
	for j in range(count,a_length):
		if -a[j] + i == m:
			heapq.heappush(l,b[j])
			count += 1
		else:
			break
	if len(l) != 0:
		maximum = heapq.heappop(l)
		ans += maximum

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

N = int(input())
S = input()
R = []
nsum = 0
for i in range(N):
    if S[i] == "R":
        R.append(i)
B = []
for i in range(N):
    if S[i] == "B":
        B.append(i)
g = 0
for i in range(N):
    if S[i] == "G":
        g += 1
        for r in R:
            for b in B:
                if abs(i - b) - abs(b - r) == 0 or abs(b - i) - abs(r - i) == 0 or abs(b - r) - abs(i - r) == 0:
                    nsum += 1
                    if max(i,b,r) == b: break
print(len(R)*len(B)*g - nsum)


### FIXED CODE ###

N = int(input())
S = input()
R = 0
G = 0
B = 0
nsum = 0
for s in S:
    if s == "R":
        R += 1
    elif s == "G":
        G += 1
    else:
        B += 1
count = 0
for i in range(N):
    for k in range(i+1,N):
        if not S[i] == S[k]:
            if 2*k - i <= N - 1:
                if S[i] != S[2*k - i] and S[k] != S[2*k - i]:
                    count += 1
print(R*G*B - count)
### BUGGY CODE ###

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

import math

Asum = sum(A)
candidates = []
for i in range(1, int(math.sqrt(Asum)) + 1):
    if Asum % i == 0:
        candidates.append(i)
        candidates.append(Asum // i)
candidates.sort()

# print("#", Asum)
# print("#", candidates)

ans = 1
for targ in candidates:
    if targ == 1: continue
    A_tmp = [(Ai % targ) for Ai in A]
    # A_tmp.sort(key=lambda x: min((x % targ), ((targ - x) % x)))
    A_tmp.sort()
    idx_l = 0
    idx_r = N - 1
    cnt = 0
    while sum(A_tmp) > 0 and idx_l < idx_r:
        cap_l = A_tmp[idx_l]
        cap_r = targ - A_tmp[idx_r]
        A_tmp[idx_l] = (A_tmp[idx_l] - min(cap_l, cap_r)) % targ
        A_tmp[idx_r] = (A_tmp[idx_r] + min(cap_l, cap_r)) % targ
        cnt += min(cap_l, cap_r)
        if A_tmp[idx_l] == 0:
            idx_l += 1
        if A_tmp[idx_r] == 0:
            idx_r -= 1
    #
    if cnt <= K and sum(A_tmp) == 0: ans = targ

print(ans)


### FIXED CODE ###

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

import math

Asum = sum(A)
candidates = []
for i in range(1, int(math.sqrt(Asum)) + 1):
    if Asum % i == 0:
        candidates.append(i)
        candidates.append(Asum // i)
candidates.sort()

# print("#", Asum)
# print("#", candidates)

ans = 1
for targ in candidates:
    if targ == 1: continue
    A_tmp = [(Ai % targ) for Ai in A]
    # A_tmp.sort(key=lambda x: min((x % targ), ((targ - x) % x)))
    A_tmp.sort()
    idx_l = 0
    idx_r = N - 1
    cnt = 0
    while sum(A_tmp) > 0 and idx_l < idx_r:
        cap_l = A_tmp[idx_l]
        cap_r = targ - A_tmp[idx_r]
        A_tmp[idx_l] = (A_tmp[idx_l] - min(cap_l, cap_r)) % targ
        A_tmp[idx_r] = (A_tmp[idx_r] + min(cap_l, cap_r)) % targ
        cnt += min(cap_l, cap_r)
        if A_tmp[idx_l] == 0:
            idx_l += 1
        if A_tmp[idx_r] == 0:
            idx_r -= 1
    #
    if cnt <= K and sum(A_tmp) == 0: ans = targ

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

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
ones = [0] * 60
zeros = [0] * 60
for i in range(N):
  x = A[i]
  x = bin(x)[2:]
  x = x.zfill(60)
  for j in range(59, -1, -1):
    if x[j] == '0':
      zeros[j] += 1
    else:
      ones[j] += 1
# print(ones)
# print(zeros)

res = 0
for i in range(N):
  x = A[i]
  x = bin(x)[2:]
  x = x.zfill(60)
  for j in range(60):
    if x[-j - 1] == '0':
      res += ones[-j - 1] * 2 ** j
      res %= MOD
      zeros[-j - 1] -= 1
    else:
      res += zeros[-j - 1] * 2 ** j
      res %= MOD
      ones[-j - 1] -= 1
print(res)

### FIXED CODE ###

def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = [sum(1 for a in A if a&(1<<i)) for i in range(60)]
  res = 0
  for i in range(60):
    res += ones[i] * (N - ones[i]) * ((2 ** i) % MOD)
    res %= MOD
  print(res)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from math import sqrt
from decimal import *

a, b, c = map(int, input().split())
getcontext().prec = 50000
if (Decimal(a).sqrt() + Decimal(b).sqrt() < Decimal(c).sqrt()): print('Yes')
else: print('No')


### FIXED CODE ###

from math import sqrt
a, b, c = map(int, input().split())
l = (a ** 2) + (b ** 2) + (c ** 2)
r = 2 * (a * b + b * c + c * a)

if (c-a-b > 0 and l > r): print('Yes')
elif(sqrt(c) == sqrt(a) + sqrt(b)): print('No')
else: print('No')
### BUGGY CODE ###

# https://atcoder.jp/contests/abc153/tasks/abc153_e


def main():
    h, n = map(int, input().split(" "))
    d = []
    c = []
    for _ in range(n):
        damage, cost = map(int, input().split(" "))
        d.append(damage)
        c.append(cost)
    dp = [float("inf")] * (h + 1)
    dp[0] = 0
    for i in range(n):
        for total in range(h +1):
            # 現在の蓄積ダメージから、魔法iを使った場合に与えるダメージ
            damage = min(total + d[i], h)
            dp[damage] = min(dp[damage], dp[total] + c[i])
    print(dp[-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

# https://atcoder.jp/contests/abc153/tasks/abc153_e


def main():
    h, n = map(int, input().split(" "))
    dp = [float("inf")] * (h + 1)
    dp[0] = 0
    for i in range(n):
        damage, cost = map(int, input().split(" "))
        for total in range(h +1):
            # 現在の蓄積ダメージから、魔法iを使った場合に与えるダメージ
            next_damage = min(total + damage, h)
            dp[next_damage] = min(dp[next_damage], dp[total] + cost)
    print(dp[-1])


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

from sys import stdin,setrecursionlimit
setrecursionlimit(10 ** 7)
n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()
point = 0
for k in range(2,len(s)):
    for j in range(1,k):
        for i in range(j):
            if s[i] != s[j] and s[i]!= s[k] and s[j] != s[k]:
                if j-i != k-j:
                    point += 1
print(point)

### FIXED CODE ###

n = int(input())
s = input()
R = s.count("R")
G = s.count("G")
B = s.count("B")
point = 0
#全ての組み合わせ
for i in range(n-2):
    for j in range(i+1,n-1):
        k = j + j-i
        if k >= n:
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            point += 1
print(R*G*B-point)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
def solve(a,w,dp):
    if not a or w==0: return 0
    if (str(a),w) in dp: return dp[(str(a),w)]
    maxx=0
    for i in range(len(a)):
        if a[i][0]<=w:
            maxx=max(maxx,a[i][1]+solve(a[:i]+a[i+1:],w-a[i][0],dp))
    dp[(str(a),w)]=maxx
    return maxx
if __name__=='__main__':
    n,w=map(int,input().split())
    a=[]
    sw=0
    for i in range(n):
        p,q=map(int,input().split())
        if p>w: continue
        a.append((p,q))
        sw+=a[-1][0]
    a.sort(key=lambda x: x[0])
    print(solve(a,w,{}))

### FIXED CODE ###

def solve(w,v,tv,W):
    dp=[float('inf')]*(tv+1)
    dp[0]=0
    for i in range(len(w)):
        for j in range(tv-v[i],-1,-1):
            dp[j+v[i]]=min(dp[j+v[i]],dp[j]+w[i])
    maxx=0
    for i in range(tv+1):
        if dp[i]<=W:
            maxx=max(maxx,i)
    return maxx
if __name__=='__main__':
    n,W=map(int,input().split())
    w=[]
    v=[]
    for i in range(n):
        p,q=map(int,input().split())
        w.append(p)
        v.append(q)
    print(solve(w,v,sum(v),W))