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

N,K = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]
mod = 10**9+7

E = [[] for _ in [0]*N]
for a,b in AB:
    E[a-1].append(b-1)
    E[b-1].append(a-1)

ans = K
q = [0]
V = [-1]*N
V[0] = [0,0]
while q:
    qq = []
    for i in q:
        tmp = sorted(set(V[i]))
        cSet = list(range(tmp[0])) + list(range(tmp[0]+1,tmp[-1])) + list(range(tmp[-1]+1,K))
        for j in E[i]:
            if V[j]!=-1:continue
            ans = ans * len(cSet) % mod
            if ans == 0:break
            qq.append(j)
            V[j] = [cSet.pop(),V[i][0]]
    q = qq
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]
mod = 10**9+7

E = [[] for _ in [0]*N]
for a,b in AB:
    E[a-1].append(b-1)
    E[b-1].append(a-1)

ans = K
q = [0]
V = [False for _ in [0]*N]
V[0] = True
while q:
    qq = []
    for i in q:
        #tmp = sorted(set(V[i]))
        #cSet = list(range(tmp[0])) + list(range(tmp[0]+1,tmp[-1])) + list(range(tmp[-1]+1,K))
        l = K-2+(i==0)
        for j in E[i]:
            if V[j]:continue
            ans = ans * l % mod
            if ans == 0:break
            qq.append(j)
            V[j] = True
            l -= 1
    q = qq
print(ans)
### BUGGY CODE ###

N = int(input())
X = str(input())

from functools import lru_cache


def popcount(bits: str):
    return len([elm for elm in bits if elm == '1'])


cache = dict()

@lru_cache(maxsize=100000)
def f(num):
    if num == 0:
        return 0
    else:
        # if not cache.get(num % pc, None) is None:
        #     return cache[num % pc]
        pc = popcount('{:b}'.format(num))
        ret = 1 + f(num % pc)
        # cache[num % pc] = ret
        return ret


def reverse_bit(bits: str, digit):
    def toggle(a):
        if a == '1':
            return '0'
        else:
            return '1'

    ret = list(bits)
    ret[digit-1] = toggle(bits[digit-1])
    return ''.join(ret)

def convert(x: str):
    ans = 0
    i = 0
    for elm in list(x)[::-1]:
        if elm == '1':
            ans += 2 ** i
        i += 1
    return ans


answers = {}

for i in range(1, N+1):
    bits = reverse_bit(X, i)
    # pc = popcount(bits)
    # print(f'# {bits} {convert(bits)} {pc}')
    x = convert(bits)
    if not answers.get(x, None) is None:
        print(answers[x])
        continue
    ret = f(x)
    answers[x] = ret
    print(ret)

### FIXED CODE ###

n = int(input())
# for i in range(n):
#     print('0', end='')
# print(flush=True)
s = input()
x = int(s, base=2)
popcount = s.count('1')
y_zero = x % (popcount + 1)
if popcount > 1:
    y_one = x % (popcount - 1)
dp = [-1] * n
dp[0] = 0
 
 
def calc(y):
    if dp[y] != -1:
        return dp[y]
    dp[y] = 1 + calc(y % bin(y).count('1'))
    return dp[y]
 
 
ans = [0] * n
rem_zero = 1
if popcount > 1:
    rem_one = popcount - 2
for i in range(n):
    if s[n - 1 - i] == '0':
        ans[n - 1 - i] = 1 + calc((y_zero + rem_zero) % (popcount + 1))
    elif popcount > 1:
        ans[n - 1 - i] = 1 + calc((y_one + rem_one) % (popcount - 1))
    else:
        ans[n - 1 - i] = 0
    rem_zero = rem_zero * 2 % (popcount + 1)
    if popcount > 1:
        rem_one = rem_one * 2 % (popcount - 1)
for i in range(n):
    print(ans[i])
### BUGGY CODE ###

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

for i in a:
    b.append(i)
    b = b[::-1]

print(*b)

### FIXED CODE ###

import collections

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

for i, num in enumerate(a):
    if i % 2 != 0:
        b.append(num)
    else:
        b.appendleft(num)

if n % 2 == 0:
    b.reverse()

print(*b)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 998244353
half = pow(2, mod - 2, mod)
maxA = max(A)


def main():
    cnt = [0] * (maxA + 1)
    for Ai in A:
        cnt[Ai] += 1

    w = [0] * (maxA + 1)
    for i in range(1, maxA + 1):
        w[i] += pow(i, mod - 2, mod)
        w[i] %= mod
        for j in range(i * 2, maxA + 1, i):
            w[j] -= w[i]
            w[j] %= mod


    def sum_cross(arr):
        s = 0
        s2 = 0
        for a in arr:
            s += a
            s2 += a ** 2
            s %= mod
            s2 %= mod
        return ((((s ** 2) % mod - s2) % mod) * half) % mod


    ans = 0
    for i in range(1, maxA + 1):
        Ai = []
        for j in range(i, maxA + 1, i):
            for k in range(cnt[j]):
                Ai.append(j)
        ans += w[i] * sum_cross(Ai)
        ans %= mod

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 998244353
half = pow(2, mod - 2, mod)
maxA = max(A) + 1


def main():
    cnt = [0] * maxA
    for Ai in A:
        cnt[Ai] += 1

    w = [pow(i, mod-2, mod) for i in range(maxA)]
    for i in range(1, maxA):
        for j in range(i * 2, maxA, i):
            w[j] = (w[j] - w[i]) % mod

    ans = 0
    for i in range(1, maxA):
        s = s2 = 0
        for j in range(i, maxA, i):
            s = (s + (j * cnt[j])) % mod
            s2 = (s2 + (j * j * cnt[j])) % mod
        ans += w[i] * ((((s ** 2) % mod - s2) % mod) * half) % mod
        ans %= mod
    print(ans)


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

N = int(input())

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return len(lower_divisors + upper_divisors[::-1])

count = 0
for i in range(1, N+1):
  count += i * make_divisors(i)

print(count)
  

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())

res = 0
for k in range(1, N+1):
    y = N // k
    res += k * y * (y+1) // 2

print(res)
### BUGGY CODE ###

N, M = map(int,input().split())
L = [0] * M
R = [0] * M
D = [0] * M
for i in range(M):
	L[i],R[i],D[i] = map(int,input().split())
#	print(L[i],R[i],D[i])
leftside = 0
cand = set()
for i in range(M):
	cand.add(L[i])
for i in range(M):
	if R[i] in cand:
		cand.remove(R[i])

res = True
if M == 0:
	res = True
else:
	if len(cand) == 0:
		res = False
	else:
		leftside = list(cand)
#		print("leftside:",leftside)
		ok = True
		for c in leftside:
			point = [-1] * (N+1)
			point[c] = 0
			ok = True
			while True:
				update = False
				for i in range(M):
					if point[L[i]] != -1:
						if point[R[i]] == -1:
							update = True
							point[R[i]] = point[L[i]] + D[i]
						else:
							if point[R[i]] != point[L[i]] + D[i]:
								ok = False
								break
				if update == False:
					break
				res &= ok
					
print("Yes" if res == True else "No")

### FIXED CODE ###

NOT_VISIT = 10**20
N, M = map(int,input().split())
graph = [[] for i in range(N)]

for i in range(M):
	L, R, D = map(int,input().split())
	graph[L-1].append((R-1,D))
	graph[R-1].append((L-1,-D))

visited = [NOT_VISIT for i in range(N)]

def dfs(start):
	global graph, visited

	if visited[start] != NOT_VISIT:
		return True

	stack = [start]
	visited[start] = 0
	while stack:
		label = stack.pop()
		for nextnode, distance in graph[label]:
			if visited[nextnode] == NOT_VISIT:
				stack.append(nextnode)
				visited[nextnode] = visited[label] + distance
			elif visited[nextnode] != visited[label] + distance:
				return False
	return True

res = True
for i in range(N):
	res &= dfs(i)

print("Yes" if res == True else "No")
### BUGGY CODE ###

N, K = map(int, input().split())
MOD = 10 ** 9 + 7
memo = {}


def c(a, b):
    if (a, b) not in memo:
        ans = 1
        for i in range(b):
            ans *= a - i
        for i in range(1, 1 + b):
            ans //= i
        memo[(a, b)] = ans
    return memo[(a, b)]


for i in range(1, 1 + K):
    ans_i = c(N - K + 1, i) * c(K - 1, i - 1)
    ans_i %= MOD
    print(ans_i)


### FIXED CODE ###

N, K = map(int, input().split())
MOD = 10 ** 9 + 7


nk1Ci = [1]
k1Ci1 = [1]
temp1 = 1
temp2 = 1
for i in range(K):
    temp1 = temp1 * (N - K + 1 - i) // (i + 1)
    temp2 = temp2 * (K - 1 - i) // (i + 1)
    nk1Ci.append(temp1)
    k1Ci1.append(temp2)


for i in range(1, 1 + K):
    ans_i = nk1Ci[i] * k1Ci1[i - 1]
    ans_i %= MOD
    print(ans_i)
### BUGGY CODE ###


# A以下の数がN個与えられる。全て素因数分解せよ。
class SpeedPrime:
    # a以下の各数の最小の素因数を記録
    def __init__(self, a):
        self.d = [i for i in range(a+1)]

        i=2
        while i*i<=a:
            if self.d[i]==i:
                j=i*i
                while j<=a:
                    if self.d[j]==j:
                        self.d[j]=i
                    j+=i
            i+=1

    # nを高速素因数分解
    def fac(self, n):
        ret = dict()
        while n!=1:
            prime=self.d[n]
            if prime in ret:
                ret[prime]+=1
            else:
                ret[prime]=1
            n=n//prime
        return ret

import math
from functools import reduce
def gcd(numbers):
    return reduce(math.gcd, numbers)

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

sp=SpeedPrime(max(a))

d=set()
pc=True
for i in a:
    prime=sp.fac(i)
    for k in prime.keys():
        if k in d:
            pc=False
            break
        else:
            d.add(k)

if pc:
    print("pairwise coprime")
    exit()

g=gcd(a)
if g==1:
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###


# A以下の数がN個与えられる。全て素因数分解せよ。
class SpeedPrime:
    # a以下の各数の最小の素因数を記録
    def __init__(self, a):
        self.d = [i for i in range(a+1)]

        i=2
        while i*i<=a:
            if self.d[i]==i:
                j=i*i
                while j<=a:
                    if self.d[j]==j:
                        self.d[j]=i
                    j+=i
            i+=1

    # nを高速素因数分解
    def fac(self, n):
        ret = dict()
        while n!=1:
            prime=self.d[n]
            if prime in ret:
                ret[prime]+=1
            else:
                ret[prime]=1
            n=n//prime
        return ret

import math
from functools import reduce
def gcd(numbers):
    return reduce(math.gcd, numbers)

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

sp=SpeedPrime(max(a))

d=set()
pc=True
for i in a:
    prime=sp.fac(i)
    for k in prime.keys():
        if k in d:
            pc=False
            break
        else:
            d.add(k)

if pc:
    print("pairwise coprime")
    exit()

g=gcd(a)
if g==1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

N = int(input())
l = []
for i in range(N):
    A = int(input())
    l.append(A)
for i in range(N):
    b = l[i]
    l[i] = 0
    print(max(l))
    l[i] = b


### FIXED CODE ###

n = int(input())
l = []
for i in range(n):
    l.append(int(input()))
m = max(l)
ans = [m]*n
if len(set(l)) == 1 or l.count(m) > 1:
    for i in ans:
        print(i)
else:
    x = sorted(set(l))[-2]
    a = l.index(m)
    ans[a] = x
    for i in ans:
        print(i)
### BUGGY CODE ###

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

### FIXED CODE ###

k, s = map(int, input().split())
c = 0
for x in range(k+1):
    for y in range(k+1):
        if ((s-x-y) <= k) & ((s-x-y) >= 0):
            c += 1
print(c)
### BUGGY CODE ###

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

def cal(a, b):
    c = [1]
    if a%2 == 0 and b%2 == 0:
        c.append(2)
    for i in range(3, min(a, b)+1, 2):
        if a%i == 0 and b%i == 0:
            if len(c) == 1:
                c.append(i)
            else:
                for j, k in enumerate(c[1:]):
                    if i%k == 0:
                        break
                    elif j == len(c)-2:
                        c.append(i)
    return c

ans = cal(a, b)
print(len(ans))


### FIXED CODE ###

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

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def cal(c):
    d = []
    while c%2 == 0:
        d.append(2)
        c //= 2
    f = 3
    while f**2 <= c:
        if c%f == 0:
            d.append(f)
            c //= f
        else:
            f += 2
    if c != 1:
        d.append(c)
    return d
    
c = gcd(a, b)
d = cal(c)
print(len(set(d))+1)
### BUGGY CODE ###

from collections import deque
N, Q = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

edge_map = [[] for i in range(N)]

for edge in edges:
    a = edge[0]
    b = edge[1]
    edge_map[a-1].append(b-1)
    edge_map[b-1].append(a-1)


counters = [0 for i in range(N)]

for operation in operations:
    p = operation[0]
    x = operation[1]
    counters[p-1] += x


res_list = [counters[i] for i in range(N)]
calculated = [False for i in range(N)]

target = [0]
while len(target) > 0:
    t = target.pop()
    calculated[t] = True
    for child in edge_map[t]:
        if calculated[child]:
            continue
        target.append(child)
        res_list[child] += res_list[t]


ans = " ".join([str(i) for i in res_list])
print(ans)


### FIXED CODE ###

from collections import deque
N, Q = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

edge_map = [[] for i in range(N)]

for edge in edges:
    a = edge[0]
    b = edge[1]
    edge_map[a-1].append(b-1)
    edge_map[b-1].append(a-1)


counters = [0]*N

for operation in operations:
    p = operation[0]
    x = operation[1]
    counters[p-1] += x


res_list = [counters[i] for i in range(N)]
calculated = [False for i in range(N)]

target = [0]
while len(target) > 0:
    t = target.pop()
    calculated[t] = True
    for child in edge_map[t]:
        if calculated[child]:
            continue
        target.append(child)
        res_list[child] += res_list[t]

print(*res_list)
### BUGGY CODE ###

R, G, B, N = map(int,input().split())

i = 0
j = 0
cnt = 0

while i*R <= N:
    while i*R + j*G <= N:
        if (N - i*R - j*G) % B == 0:
            cnt += 1
        j += 1
    j = 0

### FIXED CODE ###

R, G, B, N = map(int,input().split())
 
i = 0
j = 0
cnt = 0
 
while i*R <= N:
    while i*R + j*G <= N:
        temp = N - i*R - j*G
        if temp % B == 0:
            cnt += 1
        j += 1
    j = 0
    i += 1
 
print(cnt)
### BUGGY CODE ###

import numpy as np

h, w = map(int, input().split())
s = [['#'] * (w + 2)] + [list('#' + input() + '#') for _ in range(h)] + [['#'] * (w + 2)]
s = np.array(s)
s = (s == ".") * 1
def neext(a):
    l, m = a[0], a[1]
    return [(l, m+1), (l, m-1), (l+1, m), (l-1, m)]
def solve(i, j):
    if s[i][j] == 0:
        return 0
    else:
        p = np.full_like(s, -1)
        check = [((-1, -1), (i, j), 0)]#(from,now, dist)
        while check:
            From, now, d = check.pop(0)
            p[now[0]][now[1]] = d
            for b, c in neext((now[0], now[1])):

                if (b == From[0] and c == From[1]) or p[b][c] != -1 or s[b][c] == 0:
                    continue
                else:
                    check.append(((i, j), (b, c), d + 1))
        return np.max(p)
ans = 0
for H in range(len(s)):
    for W in range(len(s[0])):
        ans = max(ans, solve(H, W))
print(ans)

### FIXED CODE ###

import numpy as np
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = 0
for i in range(len(s)):
    for j in range(len(s[0])):
        if s[i][j] == '#':
            continue
        pre = 0
        p = np.full((h, w), -1)
        p[i][j] = 0
        check = deque([((i, j), 0)])#(from,now, dist)
        while check:
            now, d = check.popleft()
            pre = max(pre, d)
            for k, l in [(1,0), (-1,0),(0,1), (0,-1)]:
                b = now[0] + k
                c = now[1] + l
                if b < 0 or c < 0 or b >= h or c >= w:
                    continue 
                elif p[b][c] == -1 and s[b][c] != '#':
                    check.append(((b, c), d + 1))
                    p[b][c] = d + 1
        ans = max(ans, pre)

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

H, W, A, B = map(int, input().split())

MOD = 10 ** 9 + 7


def pow_mod(x, p):
    res = 1
    while p:
        if p % 2:
            res = res * x % MOD
        x = x * x % MOD
        p //= 2
    return res


F = [1]
invF = [1]


def comb_mod(n, r):
    return F[n] * invF[r] * invF[n - r] % MOD


for i in range(1, H + W - 1):
    F.append(F[-1] * i % MOD)
    invF.append(pow_mod(F[-1], 10 ** 9 + 5))

res = 0
for i in range(B + 1, W + 1):
    p = H - A - 1
    q = i - 1

    res = (
                  res
                  + comb_mod(H - A - 1 + i - 1, H - A - 1)
                  * comb_mod(A - 1 + W - i, W - i)
          ) % MOD

print(res)

### FIXED CODE ###

H, W, A, B = map(int, input().split())

MOD = 10 ** 9 + 7


def pow_mod(x, p):
    res = 1
    while p:
        if p % 2:
            res = res * x % MOD
        x = x * x % MOD
        p //= 2
    return res


F = [1]
invF = []


def comb_mod(n, r):
    return F[n] * invF[r] * invF[n - r] % MOD


for i in range(1, H + W - 1):
    F.append(F[-1] * i % MOD)

invF.append(pow_mod(F[-1], (MOD - 2)))
for f in range(len(F) - 1):
    invF.append(invF[-1] * (len(F) - len(invF)) % MOD)
invF = invF[::-1]

res = 0
for i in range(B + 1, W + 1):
    p = H - A - 1
    q = i - 1

    res = (
                  res
                  + comb_mod(H - A - 1 + i - 1, H - A - 1)
                  * comb_mod(A - 1 + W - i, W - i)
          ) % MOD

print(res)
### BUGGY CODE ###

import sys
from collections import deque


def bfs(s):
    flag_list[s] = 1
    color_list[s] = 0
    q.append(s)
    while len(q)>0:
        u = q.popleft()
        for v, w in enumerate(m_list[u]):
            if w > 0 and flag_list[v] == 0:
                flag_list[v] = 1
                if w%2 == 0:
                    color_list[v] = color_list[u]
                else:
                    color_list[v] = (color_list[u]+1)%2
                q.append(v)
        flag_list[u] = 2


if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    m_list = [[0]*n for _ in range(n)]
    color_list = [0]*n
    flag_list = [0]*n
    q = deque([])
    for _ in range(n-1):
        u, v, w = map(int, input().split())
        m_list[u-1][v-1] = w
        m_list[v-1][u-1] = w
    bfs(0)
    for color in color_list:
        print(color)


### FIXED CODE ###

import sys
from collections import deque


def bfs(s):
    color_list[s] = 0
    flag_list[s] = 1
    q.append(s)
    while len(q) > 0:
        u = q.popleft()
        for v, w in m_list[u]:
            if flag_list[v] == 0:
                flag_list[v] = 1
                if w%2 == 0:
                    color_list[v] = color_list[u]
                else:
                    color_list[v] = (color_list[u]+1)%2
                q.append(v)
        flag_list[u] = 2


if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    m_list = [[]*n for _ in range(n)]
    color_list = [0]*n
    flag_list = [0]*n
    q = deque([])
    for _ in range(n-1):
        u, v, w = map(int, input().split())
        m_list[u-1].append([v-1, w])
        m_list[v-1].append([u-1, w])
    bfs(0)
    for color in color_list:
        print(color)
### BUGGY CODE ###

import math

# def comb_count(n, r):
#     return math.factorial(n) // math.factorial(r) // math.factorial(n - r)

S = input()[::-1]
ans = 0

mods = [0] * 2019 #余りが0~2018
mods[0] = 1
current = 0
tmp = 1

for i in range(len(S)):
    current = int(S[i]) * tmp + current
    mod = current % 2019
    ans += mods[mod]
    mods[mod] += 1
    tmp = tmp * 10

# for mod in mods:
#     if mod > 1:
#         ans += comb_count(mod, 2)
print(ans)



### FIXED CODE ###

import math

# def comb_count(n, r):
#     return math.factorial(n) // math.factorial(r) // math.factorial(n - r)

S = input()[::-1]
ans = 0

mods = [0] * 2019 #余りが0~2018
mods[0] = 1
current = 0
tmp = 1

for i in range(len(S)):
    current = (int(S[i]) * tmp + current) % 2019
    mod = current % 2019
    ans += mods[mod]
    mods[mod] += 1
    tmp = tmp * 10 % 2019

# for mod in mods:
#     if mod > 1:
#         ans += comb_count(mod, 2)
print(ans)
### BUGGY CODE ###

#python3
from copy import copy
MOD = int(1e9)+7

def main():
    s = input()
    n = len(s)
    dp = [0 for _ in range(13)]
    dp[0] = 1 
    mul = 1
    for i in reversed(range(n)):
        nextDP = [0 for _ in range(13)]
        if s[i] == '?':
            for j in range(13):
                for k in range(10):
                    nextDP[(k*mul + j)%13] += dp[j]
                    nextDP[(k*mul + j)%13] %= MOD
        else:
            x = ord(s[i]) - ord('0')
            for j in range(13):
                nextDP[(x*mul + j)%13] += dp[j]
                nextDP[(x*mul + j)%13] %= MOD
        dp = copy(nextDP)
        mul *= 10
        mul %= 13
    print(dp[5])
main()

### FIXED CODE ###

from copy import copy
MOD = int(1e9)+7

def main():
    s = input()
    n = len(s)
    dp = [0 for _ in range(13)]
    dp[0] = 1 
    mul = 1
    for i in reversed(range(n)):
        nextDP = [0 for _ in range(13)]
        if s[i] == '?':
            for j in range(13):
                for k in range(10):
                    nextDP[(k*mul + j)%13] += dp[j]
                    nextDP[(k*mul + j)%13] %= MOD
        else:
            x = ord(s[i]) - ord('0')
            for j in range(13):
                nextDP[(x*mul + j)%13] += dp[j]
                nextDP[(x*mul + j)%13] %= MOD
        dp = copy(nextDP)
        mul *= 10
        mul %= 13
    print(dp[5])
main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
  n = int(input())
  A = tuple(map(int, input().split()))
  B = tuple(map(int, input().split()))
  def f(n):
    dp = list(range(n+1))
    for i in range(n+1):
      for a, b in zip(A, B):
        if i-a >= 0:
          dp[i] = max(dp[i], dp[i-a]+b)
    return max(dp)
  m = f(n)
  A, B = B, A
  ans = f(m)
  print(ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
def f(n):
  dp = list(range(n+1))
  for a, b in zip(A, B):
    for i in range(n+1):
      if i-a >= 0:
        dp[i] = max(dp[i], dp[i-a]+b)
  return max(dp)
m = f(n)
A, B = B, A
ans = f(m)
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
a_list=[]
pass_1= []
for i in range(M):
    a = list(map(int,input().split()))
    if(a[0]==1):
        pass_1.append(a[1])
    else:
        a_list.append(a)
    
for j in pass_1:
    if([j,N] in a_list):
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

### FIXED CODE ###

N,M = map(int,input().split())
a_list=[]
pass_1= []
for i in range(M):
    a = list(map(int,input().split()))
    if(a[0]==1):
        pass_1.append(a[1])
    elif(a[1]==N):
        a_list.append(a[0])
    
if list(set(pass_1) & set(a_list)):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')