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

import sys
from operator import itemgetter
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
def main():
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while(e[0] > d):
			if cont == True:
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			else:
				mini = min(kouho)
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			cont = True
			if q < Q-1:
				q = q + 1
				d = int(inputs())
			else:
				flag = True
				q = q + 1
				break
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
		
def sub():
	V = [list(map(int,inputs().split())) for p in [0]*N]
	M = [int(inputs()) for p in [0]*Q]
	V.sort(key = lambda x:(x[2],x[0],x[1]))
	for v in V:
		v[0] -= v[2]
		v[1] -= v[2] + 1
	for m in M:
		for n in range(N):
			if V[n][0] <=m and m <= V[n][1]:
				print(V[n][2])
				break
		else:
			print(-1)


if N>190000:
	sub()
else:
	main()

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###

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

ave = M//N
amari = M%N
while True:
  if amari%ave == 0:
    ans = ave
    break
  else:
    ave -= 1
    amari = M%ave
print(ans)  

### FIXED CODE ###

N,M = map(int,input().split())
ave = M//N
amari = M%N
while True:
  if amari%ave == 0:
    ans = ave
    break
  else:
    ave -= 1
    amari = M%ave
print(ans)
### BUGGY CODE ###

import re
from collections import Counter
n, q = map(int, input().split())
s = input()
for _ in range(q):
    l, r = map(int, input().split())
    word = re.findall('AC', s[l-1:r])
    C = Counter(word)
    print(C['AC'])

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
t = [0] * (n + 1)
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2]=='AC' else 0)
for i in range(q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

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


def solve():
    N = int(input())
    A = []
    checked = [False for _ in range(N)]
    count = 0
    for _ in range(N):
        A.append(int(input()))
    for i, a in enumerate(reversed(A)):
        i = N - 1 - i  # reversed index
        # print('searching:', i, ',', a)
        if checked[i]:
            # print('checked')
            continue
        count += 1
        searching = a
        for j, b in enumerate(reversed(A[:i])):
            # print(A[:i])
            j = i - j - 1
            # print(i, j, b)
            if b >= searching or checked[j]:
                continue
            searching = b
            checked[j] = True
            # print('check:', j, ',', b)
    return count
  

def main():
    print(solve())


if __name__ == "__main__":
    main()


### FIXED CODE ###

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

import bisect as bi


def solve():
    N = int(input())
    A = []
    heads = []
    for _ in range(N):
        A.append(int(input()))
    a = A.pop()
    bi.insort(heads, a)
    while A:
        a = A.pop()
        if a < heads[-1]:
            j = bi.bisect(heads, a)
            del heads[j]
        bi.insort(heads, a)
    return len(heads)
  

def main():
    print(solve())


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

def main():
    k,s = map(int,input().split())
    cnt = 0

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

### FIXED CODE ###

def main():
    k,s = map(int,input().split())
    cnt = 0

    for x in range(k+1):
        for y in range(k+1):
            if 0 <= s-(x+y) <= k:
                cnt+=1
    print(cnt)
main()
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
# print(N, H)

ret = 'Yes'

for i in range(N):
	for j in range(i, N):
		if H[i]-1 > H[j]:
			ret = 'No'
			break

	if ret == 'No':
		break

print(ret)


### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))

ret = 'Yes'
bar = H[0] - 1

for i in range(1, N):
	if bar > H[i]:
		ret = ('No')
		break
	elif bar < H[i]:
		bar = H[i] - 1

print(ret)
### BUGGY CODE ###

#!/usr/bin/env pypy3
# n,m = map(int,sys.stdin.readline().split())
# a = list(map(int,sys.stdin.readline().split()))
# a = [sys.stdin.readline() for s in range(n)]
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
# d = collections.defaultdict(list)
# import math
# from functools import reduce
import sys
sys.setrecursionlimit(15000)

n = int(sys.stdin.readline())
s = sys.stdin.readline().rstrip()
d = {"R":[],"G":[],"B":[]}
for i in range(n):
    d[s[i]].append(i)
s = 0
for a in d["R"]:
    for b in d["G"]:
        for c in d["B"]:
            if abs(a-b) != abs(b-c) and abs(a-c) != abs(c-b) and abs(b-a) != abs(a-c):
                s += 1
print(s)


### FIXED CODE ###

#!/usr/bin/env pypy3
# n,m = map(int,sys.stdin.readline().split())
# a = list(map(int,sys.stdin.readline().split()))
# a = [sys.stdin.readline() for s in range(n)]
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
# d = collections.defaultdict(list)
# import math
# from functools import reduce
import sys
sys.setrecursionlimit(15000)

n = int(sys.stdin.readline())
s = sys.stdin.readline().rstrip()
d = {"R":[],"G":[],"B":[]}
sb = set()
for i in range(n):
    d[s[i]].append(i)
    if s[i]=="B":
        sb.add(i)
s = 0
#s = sum(1 for a in d["R"] for b in d["G"] for c in d["B"] if abs(a-b) != abs(b-c) and abs(a-c) != abs(c-b) and abs(b-a) != abs(a-c))
#s = len(d["R"])*len(d["G"])*len(d["B"])-sum(1 for a in d["R"] for b in d["G"] for c in d["B"] if abs(a-b) == abs(b-c) or abs(a-c) == abs(c-b) or abs(b-a) == abs(a-c))
for a in d["R"]:
    for b in d["G"]:
        s += len(d["B"])
        if 2*b-a in sb:
            s -= 1
        if 2*a-b in sb:
            s -= 1
        if (a+b)%2 == 0 and (a+b)//2 in sb:
            s -= 1
print(s)
### BUGGY CODE ###

import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))

    dist = [[float('inf')] * N for _ in range(N)]
    for a, b, c in (map(int, input().split()) for _ in range(M)):
        dist[a-1][b-1] = dist[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = dist[i][j] if dist[i][j] < dist[i][k] + dist[k][j] else dist[i][k] + dist[k][j]

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i] - 1
            b = r[i+1] - 1
            move += dist[a][b]
        ans = ans if ans < move else move

    print(ans)

main()


### FIXED CODE ###

import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf')] * (N + 1) for j in range(N + 1)]
    for a, b, c in ABC:
        dist[a][b] = dist[b][a] = c
        dist[a][a] = dist[b][b] = 0
    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i]
            b = r[i+1]
            move += dist[a][b]
        ans = min(ans, move)

    print(ans)

main()
### BUGGY CODE ###

import math
from collections import deque

def parent(i):
    return math.floor(i / 2)

def get_largest(i):
    l = i << 1
    r = l + 1
    largest = None
    size = len(A) - 1
    if l <= size and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r <= size and A[largest] < A[r]:
        largest = r
    return largest


def max_heapify(i):
    largest = get_largest(i)
    x = i
    while largest is not x:
        tmp = A[x]
        A[x] = A[largest]
        A[largest] = tmp
        x = largest
        largest = get_largest(x)

def extract():
    m = A[1]
    A[1] = A[-1]
    A.pop()
    max_heapify(1)
    return m

def insert_key(key):
    A.append(key)
    i = len(A) - 1
    while 1 < i and A[parent(i)] < A[i]:
        tmp = A[i]
        A[i] = A[parent(i)]
        A[parent(i)] = tmp
        i = parent(i)

inp = input()
A = deque()
A.append(0)

while True:
    if inp == 'end':
        break
    elif inp[0] == 'e':
        print(extract())
    elif inp[0] == 'i':
        insert_key(int(inp[7:]))
    inp = input()

### FIXED CODE ###

import math
import heapq

A = []
inp = input()
while True:
    if inp == 'end':
        break
    elif inp[0] == 'e':
        print(-heapq.heappop(A))
    elif inp[0] == 'i':
        heapq.heappush(A, -int(inp[7:]))
    inp = input()
### BUGGY CODE ###

H,W,m = map(int,input().split())
h = [0]*(H+1)
w = [0]*(W+1)
c = [[-1] for i in range(H+1)]
for i in range(m):
    a,b = map(int,input().split())
    h[a] += 1
    w[b] += 1
    c[a].append(b)
mh = max(h)
mw = max(w)
hkouho = []
wkouho = []
for i in range(H+1):
    if h[i] == mh:
        hkouho.append(i)
for i in range(W+1):
    if w[i] == mw:
        wkouho.append(i)
for i in hkouho:
    for j in wkouho:
        if j not in c[i]:
            print(mh+mw)
            exit()
print(mh+mw-1)

### FIXED CODE ###

import time
from bisect import bisect_left
t = time.time()
H,W,m = map(int,input().split())
h = [0]*(H+1)
w = [0]*(W+1)
c = [[-1,10**6] for i in range(H+1)]
for i in range(m):
    a,b = map(int,input().split())
    h[a] += 1
    w[b] += 1
    c[a].append(b)
mh = max(h)
mw = max(w)
hkouho = []
wkouho = []
for i in range(H+1):
    if h[i] == mh:
        hkouho.append(i)
for i in range(W+1):
    if w[i] == mw:
        wkouho.append(i)
for i in range(H+1):
    c[i].sort()
# print(hkouho)
# print(wkouho)
for i in hkouho:
    for j in wkouho:
        # print(c[i],i,j,bisect_left(c[i],j))
        if c[i][bisect_left(c[i],j)] != j:
            print(mh+mw)
            exit()
        if time.time()-t > 2.7:
            print(mh+mw-1)
            exit()
print(mh+mw-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys 
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, K = map(int, readline().split())
S = [readline().decode().rstrip() for _ in range(H)]
INF = 10**30
data = [[0]*W for _ in range(H)]
for i in range(H):
    cnt = 0 
    for j in range(W):
        if S[i][j] == '1':
            cnt +=1
        data[i][j] = cnt
data = np.array(data)

ans_cnt = INF   
for bit_H in range(1 << (H-1)):
    cnt = 0
    ans = []
    new_data = []
    for i in range(H-1):
        if (bit_H >> i) & 1:
            ans.append(i)
    ans.append(H-1)
    tmp = [0]*W
    for i in range(H):
        tmp += data[i]
        if i in ans:
            new_data.append(tmp)
            tmp = [0]*W
    new_data = np.array(new_data)
    l = len(new_data)
    cnt += l-1
    for i in range(W):
        max_cnt = new_data.max(axis=0)[i]
        if max_cnt > K and i >=1:
            cnt +=1
            for j in range(l):
                new_data[j] -= new_data[j][i-1]
        max_cnt = new_data.max(axis=0)[i]
        if max_cnt > K:
            cnt = INF
            break 
    ans_cnt = min(ans_cnt,cnt)
print(ans_cnt)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, K = map(int, readline().split())
S = [readline().decode().rstrip() for _ in range(H)]
INF = 10**30
data = [[0]*W for _ in range(H)]
for i in range(H):
    cnt = 0 
    for j in range(W):
        if S[i][j] == '1':
            data[i][j] += 1

ans_cnt = INF   
for bit_H in range(1 << (H-1)):
    cnt = 0
    ans = []
    new_data = []
    for i in range(H-1):
        if (bit_H >> i) & 1:
            ans.append(i)
    ans.append(H-1)
    tmp = [0]*W
    for i in range(H):
        for j in range(W):
            tmp[j] += data[i][j]
        if i in ans:
            new_data.append(tmp)
            tmp = [0]*W
    group = len(new_data)
    cnt += group-1
    white = [0] * group
    flag = True
    for i in range(W):
        diff = [0] * group
        for j in range(group):
            diff[j] += new_data[j][i]
            white[j] += new_data[j][i]
        max_diff = max(diff)
        if max_diff > K:
            flag = False
            break
        max_white = max(white)
        if max_white > K:
            cnt +=1
            white = diff[:]
    if flag:
        ans_cnt = min(ans_cnt,cnt)
print(ans_cnt)
### BUGGY CODE ###

import sys
import math

def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0

    while True:
        prime = min(A)

        if prime > math.sqrt(limit):
            break

        P.append(prime)

        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1

    for a in A:
        P.append(a)

    return set(P)

max_n = 10**5

primes = eratosthenes(max_n)
# print(primes)

acum_like_n = [0] * (max_n+1)
for i in range(1, max_n + 1):
    if i in primes and (i+1)//2 in primes:
        acum_like_n[i] = acum_like_n[i-1] + 1
    else:
        acum_like_n[i] = acum_like_n[i-1]
# print(acum_like_n)

Q = int(sys.stdin.readline().strip())
for _ in range(Q):
    l, r = map(int, sys.stdin.readline().strip().split())
    print(acum_like_n[r] - acum_like_n[l-1])

### FIXED CODE ###

import sys
import math

def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0

    while True:
        prime = min(A)

        if prime > math.sqrt(limit):
            break

        P.append(prime)

        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1

    for a in A:
        P.append(a)

    return set(P)

max_n = 10**5

primes = eratosthenes(max_n)
# print(primes)

acum_like_n = [0] * (max_n+1)
for i in range(1, max_n + 1):
    if i in primes and (i+1)//2 in primes:
        acum_like_n[i] = acum_like_n[i-1] + 1
    else:
        acum_like_n[i] = acum_like_n[i-1]
# print(acum_like_n)

Q = int(sys.stdin.readline().strip())
for _ in range(Q):
    l, r = map(int, sys.stdin.readline().strip().split())
    print(acum_like_n[r] - acum_like_n[l-1])
### BUGGY CODE ###

#abc164-4
s = input()

counts = [0 for _ in range(2019)]#modの値と個数を記録するリスト
d = 0
counts[0] += 1
for i in range(0,len(s)):
    d += int(s[-i-1])*(10**i)
    #print(d, d%2019)
    counts[d % 2019] += 1
#print(counts)
sumcount = 0
for m in counts:
    sumcount += m*(m-1)/2
print(int(sumcount))
#TLE

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

N = int(input())
arr = []
product = 1
# while i < N:
arr = ((input().split(' ')))

for i in arr:
    if( int(i) == 0):
        exit
    product = product * int(i)

if product <= (10**18):
    print(product)
else:
    print(-1)

### FIXED CODE ###

def main ():
    N = int(input())
    A = list(map(int,input().split()))
    if 0 in A: 
        print (0)
        return
    prod = 1 
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return
    print(prod) 

main ()
### BUGGY CODE ###

s=input()
count=0
while True:
    flag=0
    f=s[0]
    for i in range(len(s)):
        if f == '-':
            f=s[i]
        elif f != s[i]:
            count += 2
            s=s[:i-1]+"--"+s[i+1:]
            flag=1
            f='-'
    s=s.replace("-","")
    if len(s)==0 or flag ==0:
        break
print(count)


### FIXED CODE ###

s=input()

print(min(s.count("0"),s.count("1"))*2)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
[print(A[i-1:].count(i)) for i in range(1,N+1)]

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = [0] * (N+1)
for i in A:
    ans[i] += 1
for a in ans[1:]:
    print(a)
### BUGGY CODE ###

def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]

    white, black = [], []
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                black.append([i, j])
            else:
                white.append([i, j])

    ans = 0
    for bx, by in black:
        for wx, wy in white:

            queue = [[bx, by]]
            visited = [[False for i in range(w + 1)] for j in range(h+1)]
            while len(queue) != 0:
                p = queue.pop(0)
                visited[p[0]][p[1]] = True
                if p[0] == wx and p[1] == wy:
                    ans += 1
                    break
                for x, y in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                    nx = p[0] + x
                    ny = p[1] + y
                    if nx < 0 or ny < 0 or nx >= h or ny >= w or visited[nx][ny] == True:
                        continue
                    #print(nx, ny, s)
                    if (((nx+ny) % 2) == ((bx+by) % 2) and s[nx][ny] == ".") or (((nx+ny) % 2) != ((bx+by) % 2) and s[nx][ny] == "#"):
                        continue
                    queue.append([nx, ny])

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    start = []
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#": 
                start.append([i,j])

    ans = [0,0]
    vis = [[-1 for i in range(w)] for j in range(h)]
    def f(x, y, pre):
        vis[x][y] = 1
        if s[x][y] == "#":
            ans[0] += 1
        else:
            ans[1] +=1
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx = i + x
            ny = j + y
            if nx >= 0 and ny >= 0 and nx < h and ny < w and vis[nx][ny] == -1:
                if pre == "B" and s[nx][ny] == ".":
                    f(nx,ny,"W")
                elif pre == "W" and s[nx][ny] == "#":
                    f(nx, ny, "B")
                
    
    ret = 0
    for i, j in start:
        if vis[i][j] == -1:
            f(i, j, "B")
        ret += ans[0] * ans[1]
        ans[0] = ans[1] = 0
    print(ret)
        

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

X, Y, Z, K = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
*C, = map(int, input().split())
A.sort(reverse=True)

D = [i+j for j in C for i in B]
D.sort(reverse=True)
E = [i+j for j in D[:K] for i in A[:K]]
E.sort(reverse=True)

print(*E[:K], sep="\n")

### FIXED CODE ###

from heapq import heappush, heappop

X, Y, Z, K = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
*C, = map(int, input().split())
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

# x以上のものがK個あるならOK
def f(x):
    cnt = 0
    for i in A:
        for j in B:
            for k in C:
                if i+j+k<x:break
                cnt += 1
                if cnt>=K:
                    return True
    return False

def get_boarder():
    l, r = 0, A[0]+B[0]+C[0]
    while r-l>1:
        m = (l+r)//2
        if f(m):
            l = m
        else:
            r = m
    return l

boarder = get_boarder()
q = []
for i in A:
    for j in B:
        for k in C:
            if i+j+k<boarder:break
            heappush(q, -(i+j+k))

for _ in range(K):
    print(-heappop(q))
### BUGGY CODE ###

N = int(input())
A = [[0, 0]for i in range(N)]
for i in range(N):
  A[i][0], A[i][1] = map(int, input().split())
a = [0, 0]

def max1(L, p):
  a = L[0][p]
  ix = 0
  for i in range(1, len(L)):
    if a > L[i][p]:
      a = L[i][p]
      ix = i
  return ix

for i in range(N):
  j = i % 2
  idx = max1(A, j)
  a[j] += A[idx][j]
  del A[idx]

print(a[0]-a[1])

### FIXED CODE ###

N = int(input())
A = [[0, 0, 0]for i in range(N)]
for i in range(N):
  a, b = list(map(int, input().split()))
  A[i] = a+b, a, b
A.sort(reverse=True)
x = 0
for i in range(N):
    x += (-1)**i * A[i][1+i%2]
print(x)
### BUGGY CODE ###

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

values = []
weights = []

for _ in range(N):
    w, v = map(int, input().strip().split())
    weights.append(w)
    values.append(v)
    
dp = [0]*(W+1)
for i in range(N):
    curr_v = values[i]
    curr_w = weights[i]
    for w in range(W, weights[i] - 1, -1):
        dp[w] = max(dp[w], curr_v + dp[w - curr_w])

print(dp[W])

### FIXED CODE ###

N, W = map(int, input().strip().split())
 
values = []
weights = []
 
for _ in range(N):
    w, v = map(int, input().strip().split())
    weights.append(w)
    values.append(v)
    
dp = [0]*(W+1)
for i in range(N):
    for w in range(W, weights[i] - 1, -1):
        dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
print(dp[W])
### BUGGY CODE ###

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

res = 1
check = 10**18
for i in range(n):
    res *= a[i]
    if res > check :
        res = -1
print(res)

### FIXED CODE ###

n = int(input())
ls = list(map(int, input().split()))
res = 1
if 0 in ls:
    res = 0
for x in ls:
    res *= x
    if res > 10**18:
        res = -1
        break
print(res)
### BUGGY CODE ###

N = int(input())

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

b_list = list(range(1, N+1))
c_list = []
for i in range(N):
    sr = b_list[i]
    g = int(a.count(sr))
    c_list.append(g)

print(*c_list, sep='\n')

### FIXED CODE ###

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

ans = [0]*N
for i in range(len(A)):
    tmp = A[i]
    ans[tmp-1] += 1


for a in ans:
    print(a)
### BUGGY CODE ###

x = int(input())
res_list = [1]
for b in range(1,x+1):
    for p in range(2,x+1):
        if b**p <= x:
            res_list.append(b**p)
print(max(res_list))

### FIXED CODE ###

x = int(input())
res_list = [1]
for b in range(1,x+1):
    for p in range(2,x+1):
        if b**p <= x:
            res_list.append(b**p)
        else:
            break
print(max(res_list))
### BUGGY CODE ###

k,s = map(int, input().split())
cnt = 0
for i in range(0,k+1):
  for j in range(0, k+1):
    for l in range(0,k+1):
      if i+j+l == s:
        cnt += 1
print(cnt)

### FIXED CODE ###

k,s = map(int, input().split())
cnt = 0
for i in range(0,k+1):
  for j in range(0, k+1):
    z = s - i - j
    if 0<=z<=k:
      cnt += 1
print(cnt)
### BUGGY CODE ###

n, k = (int(x) for x in input().split())

c = {} 
t = 0
for x in range(k, 0, -1):
    c[x] = (k // x) ** n
    c[x] = c[x] - sum(c[x * y] for y in range(2, k // x + 1))
    s = c[x] * x
    t += s
    t = t % 1000000007

print(t)

### FIXED CODE ###

n, k = (int(x) for x in input().split())
c = {} 
t = 0
MOD = 1000000007
for x in range(k, 0, -1):
    q = k // x
    c[x] = pow(q, n, MOD) - sum(c[x * y] for y in range(2, q + 1))
    t += c[x] * x
    t = t % 1000000007
print(t)