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

class Tree:
    value=0
    def __init__(self,position):
        self.position = position
        self.kid = set()
        self.value = 0

    def add_kid(self,it):
        self.kid.add(it)

    def add_val(self,val):
        self.value += val

    def calc(self,val=0):
        self.add_val(val)
        # print("called",self.position)
        for i in self.kid:
            if(i.position in visited):
                continue
            visited.add(i.position)
            i.calc(self.value)

    def print_val(self):
        print(self.value,end=" ")


N,Q = [int(x) for x in input().split()]
ki = [Tree(i) for i in range(N)]

for i in range(N-1): #O(N)
    a,b = [int(x) for x in input().split()]
    ki[a-1].add_kid(ki[b-1])
    ki[b-1].add_kid(ki[a-1])

for i in range(Q): #O(Q)
    position,val = [int(x) for x in input().split()]
    ki[position-1].add_val(val)

visited = set()
visited.add(0)
ki[0].calc() #Recursion

for i in ki:
    i.print_val()
print()


### FIXED CODE ###

N,Q = [int(x) for x in input().split()]
ki = [0]*N
tr = [[] for _ in range(N)]

for i in range(N-1):
    a,b = [int(x)-1 for x in input().split()]
    tr[a].append(b)
    tr[b].append(a)

for i in range(Q):
    position,val = [int(x) for x in input().split()]
    ki[position-1] += val

stack =[0]
visited = set()
visited.add(0)

while stack:
    i = stack.pop()
    for j in tr[i]:
        if j in visited:
            continue
        visited.add(j)
        ki[j] += ki[i]
        stack.append(j)

for i in ki:
    print(i,end=" ")
print()
### BUGGY CODE ###

N = int(input())
P = list(map(float,input().split()))
dp = []
for i in range(N+1):
  L = [0]*(N+1)
  dp.append(L)
dp[1][0] = 1-P[0]
dp[1][1] = P[0]
for i in range(2,N+1): 
  for j in range(N+1):
    if j != 0:
      dp[i][j] = dp[i-1][j-1]*P[i-1]+dp[i-1][j]*(1-P[i-1])
    else:
      dp[i][0] = dp[i-1][0]*(1-P[i-1])
ans = 0
for i in range(N//2+1,N+1):
  ans += dp[N][i]
print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(float,input().split()))
dp = []
for i in range(N+1):
  L = [0]*(N+1)
  dp.append(L)
dp[1][0] = 1-P[0]
dp[1][1] = P[0]
for i in range(2,N+1): 
  for j in range(N+1):
    if j != 0:
      dp[i][j] = dp[i-1][j-1]*P[i-1]+dp[i-1][j]*(1-P[i-1])
    else:
      dp[i][0] = dp[i-1][0]*(1-P[i-1])
ans = 0
for i in range(N//2+1,N+1):
  ans += dp[N][i]
print(ans)
### BUGGY CODE ###

import sys
## io
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
## dp
INIT_VAL = 0
MD2 = lambda d1,d2: [[INIT_VAL]*d2 for _ in range(d1)]
MD3 = lambda d1,d2,d3: [MD2(d2,d3) for _ in range(d1)]
## math
DIVC = lambda x,y: -(-x//y)
DIVF = lambda x,y: x//y

def main():
    s = IS()
    n = len(s)
    cnt = 0
    for i in reversed(range(3,n)):
        if int(s[i-1])%2 == 0:
            if int(s[i])%2 == 0: pass
            else: continue
        for j in reversed(range(0,i-3)):
            if int(s[j:i+1])%2019 == 0:
                cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
## io
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
## dp
INIT_VAL = 0
MD2 = lambda d1,d2: [[INIT_VAL]*d2 for _ in range(d1)]
MD3 = lambda d1,d2,d3: [MD2(d2,d3) for _ in range(d1)]
## math
DIVC = lambda x,y: -(-x//y)
DIVF = lambda x,y: x//y

def main():
    s = list(map(int, IS()))
    n = len(s)
    p = 2019
    cnt = 0
    d = [0]*p
    d[0] = 1 # 0(mod p)はそれ単体で割り切れるため+1しておく
    ss = 0
    x = 1
    for si in s[::-1]:
        ss += x*si
        ss %= p
        d[ss] += 1
        x = (10*x)%p # %p無しだとTLE
    cnt = 0
    for di in d:
        cnt += di*(di-1)//2 # calc combination(n_C_2)
    print(cnt)

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

n = int(input())
a = list(map(int,input().split()))
q = int(input())
b,c = [],[]
for i in range(q):
    B,C = map(int,input().split())
    b.append(B)
    c.append(C)
for i in range(q):
    while b[i] in a:
        a.remove(b[i])
        a.append(c[i])
    print(sum(a))


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
q = int(input())
res = sum(a)
temp = [0]*100001
for x in a:
    temp[x] += 1
for i in range(q):
    b,c = map(int,input().split())
    res -= b*temp[b]
    temp[c] += temp[b]
    res += c*temp[b]
    temp[b] = 0
    print(res)
### BUGGY CODE ###

import collections

N = int(input())
s = [list(input()) for i in range(N)]

cnts = []
for i in s:
        cnts.append(collections.Counter(i))

ans = 0
for c in cnts:
        tmp = cnts.count(c)
        if tmp > 1:
                ans += tmp - 1

print(ans // 2)


### FIXED CODE ###

N = int(input())
s = [list(sorted(input())) for i in range(N)]
s.sort()

ans = []
tmp = 1
for idx,val in enumerate(s):
        if idx == 0:
                continue
        if val == s[idx - 1]:
                tmp += 1
        else:
                ans.append(tmp)
                tmp = 1
else:
        ans.append(tmp)

res = 0
for i in ans:
        res += (i * (i - 1)) // 2
print(res)
### BUGGY CODE ###

from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(lambda x: int(x)-1, input().split()))

INF = 10**9
cost = [[INF]*N for _ in range(N)]
for _ in range(M):
  A, B, C = map(int, input().split())
  A -= 1
  B -= 1
  cost[A][B] = C
  cost[B][A] = C

for k in range(N):
  for i in range(N):
    for j in range(N):
      cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])

ans = INF

for route in permutations(r):
  temp = 0
  for i in range(R-1):
    temp += cost[route[i]][route[i+1]]
  ans = min(ans, temp)

print(ans)

### FIXED CODE ###

from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(lambda x: int(x)-1, input().split()))

INF = 10**9
cost = [[INF]*N for _ in range(N)]
for _ in range(M):
  A, B, C = map(int, input().split())
  A -= 1
  B -= 1
  cost[A][B] = C
  cost[B][A] = C

for k in range(N):
  for i in range(N):
    for j in range(N):
      cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])

ans = INF

for route in permutations(r):
  temp = 0
  for i in range(R-1):
    temp += cost[route[i]][route[i+1]]
  ans = min(ans, temp)

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

from operator import mul #掛け算をする関数
from functools import reduce

def cmb(n,r):
    r = min(n-r,r) #nCrとnCn-rは等しいので小さい方を選ぶ
    if r == 0: return 1 #nC0 = 1より
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N, M, K = map(int, input().split())
ans = 0
col = M
mod = 998244353

for i in range(N)[::-1]:
    now = col
    # print('i:{}'.format(i))
    # print('col:{}'.format(col))
    now *= cmb(N-1,i)
    # print('cmb:{}'.format(cmb(N-1, i)))
    if i <= K:
        ans += now
        # print('\ni:{} now:{} ans:{}'.format(i, now, ans))
    col *= M-1

print(ans%mod)


### FIXED CODE ###

import sys

input = sys.stdin.readline

def comb(n, r):
    return (fact[n] * revfact[n-r] * revfact[r]) % mod

mod = 998244353
N, M, K = map(int, input().split())

fact = [1] * (N + 1)
for i in range(1, N + 1):
    fact[i] = (fact[i-1] * i) % mod #n!を計算
# print('fact:{}'.format(fact))
revfact = [1] * (N + 1) #逆元を定義
revfact[N] = pow(fact[N], mod - 2, mod) #n!のmod-2乗を計算
# print('revfact:{}'.format(revfact))
for i in reversed(range(1, N)): #N-1から1まで
    revfact[i] = ((i + 1) * revfact[i + 1]) % mod
# print('revfact:{}'.format(revfact))

ans = 0
for k in range(K + 1):
    ans += (M * pow(M - 1, N - 1 - k, mod) * comb(N - 1, k)) % mod
    ans %= mod
print(ans)
### BUGGY CODE ###

import re
S = input()

result = 0
while re.search(r'01|10', S):
    S = re.sub(r'01|10', '', S, 1)
    result += 2
print(result)


### FIXED CODE ###

S = input()
temp0 = S[:int(len(S)/2)]
temp1 = S[int(len(S)/2):]
temp01 = min(temp0.count('0'), temp1.count('1'))
temp10 = min(temp0.count('1'), temp1.count('0'))
print(temp01 * 2 + temp10 * 2)
### BUGGY CODE ###

import math

K = int(input())

total = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            ab = math.gcd(a, b)
            total += math.gcd(ab, c)

print(total)

### FIXED CODE ###

import math

K = int(input())

total = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        ab = math.gcd(a, b)
        for c in range(1, K + 1):
            total += math.gcd(ab, c)

print(total)
### BUGGY CODE ###

import math
count = 0  
k = int(input())
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      d = math.gcd(a,b)
      e = math.gcd(d,c)
      count += e
print(count)

### FIXED CODE ###

import math
count = 0  
k = int(input())
for a in range(1,k+1):
  for b in range(a,k+1):
    for c in range(b,k+1):
      d = math.gcd(a,b)
      e = math.gcd(d,c)
      if a==b==c:
        count+=e
      elif a==b or b==c or c==a:
        count+=e*3
      else:
        count+=e*6
print(count)
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    *N, = map(int, open(0).read().split())
    A = N[1:]
    N = N[0]

    cnt = 0
    for i in A:
        if i % 2 == 0:
            for j in range(0, max(A)):
                i = i//2
                cnt = cnt + 1
                if (i < 2) or not (i % 2 == 0):
                    break
    print(cnt)


main()

### FIXED CODE ###

#!/usr/bin/env python3

def main():
    *N, = map(int, open(0).read().split())
    A = N[1:]
    N = N[0]

    cnt = 0
    for i in A:
        if i % 2 == 0:
            for j in range(0, max(A)):
                i = i//2
                cnt = cnt + 1
                if (i < 2) or not (i % 2 == 0):
                    break
    print(cnt)


main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

N, T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1])

def dfs(i, sum, time, remain):
    global answer
    if i == N:
        if time < T and len(remain) >= 1:
            sum += AB[max(remain)][1]
        if sum > answer:
            answer = sum
    else:
        dfs(i+1, sum, time, remain)
        if time < T:
            dfs(i+1, sum + AB[i][1], time + AB[i][0], remain-{i})

answer = 0
dfs(0, 0, 0, set(range(N)))
print(answer)

### FIXED CODE ###

import sys
import numpy as np

n, t = map(int, input().split())
knapsack = np.zeros(t, dtype=np.int64)
cuisines = [tuple(map(int, line.split())) for line in sys.stdin]
cuisines.sort()
tmp_ans = 0
for a, b in cuisines:
    tmp_ans = max(tmp_ans, knapsack.max() + b)
    knapsack[a:] = np.maximum(knapsack[a:], knapsack[:-a] + b)
print(tmp_ans)
### BUGGY CODE ###

N = int(input())
Xmi, Xma, Ymi, Yma, DYmi, DYma, UYmi, UYma, RXmi, RXma, LXmi, LXma = [(10**10), -(10**10)] * 6
for _ in range(N):
    x, y, d = input().split()
    x, y = int(x), int(y)
    
    if d == "R":
        RXmi = min(RXmi, x)
        RXma = max(RXma, x)
    elif d == "L":
        LXmi = min(LXmi, x)
        LXma = max(LXma, x)
    else:
        Xmi = min(Xmi, x)
        Xma = max(Xma, x)
        
    if d == "U":
        UYmi = min(UYmi, y)
        UYma = max(UYma, y)
    elif d == "D":
        DYmi = min(DYmi, y)
        DYma = max(DYma, y)
    else:
        Ymi = min(Ymi, y)
        Yma = max(Yma, y)

def calc(t):
    xmi = min(RXmi+t, LXmi-t, Xmi)
    xma = max(RXma+t, LXma-t, Xma)
    ymi = min(UYmi+t, DYmi-t, Ymi)
    yma = max(UYma+t, DYma-t, Yma)
    return max(yma-ymi, 0)*max(xma-xmi, 0)

mi = 10**20
import random
import time
sTime = time.time()
while time.time()-sTime < 4.5:
    l = 0
    r = 10**(random.randrange(10000)/1000)
    for _ in range(100):
        m1 = (l*2+r)/3
        m2 = (l+r*2)/3
        if calc(m1) > calc(m2):
            l = m1
        else:
            r = m2
    mi = min(mi, calc(m1))


print(mi)

### FIXED CODE ###

from decimal import *
getcontext().prec = 100
N = int(input())
Xmi, Xma, Ymi, Yma, DYmi, DYma, UYmi, UYma, RXmi, RXma, LXmi, LXma = [(10**10), -(10**10)] * 6
for _ in range(N):
    x, y, d = input().split()
    x, y = int(x), int(y)
    
    if d == "R":
        RXmi = min(RXmi, x)
        RXma = max(RXma, x)
    elif d == "L":
        LXmi = min(LXmi, x)
        LXma = max(LXma, x)
    else:
        Xmi = min(Xmi, x)
        Xma = max(Xma, x)
        
    if d == "U":
        UYmi = min(UYmi, y)
        UYma = max(UYma, y)
    elif d == "D":
        DYmi = min(DYmi, y)
        DYma = max(DYma, y)
    else:
        Ymi = min(Ymi, y)
        Yma = max(Yma, y)

def calc(t):
    xmi = min(RXmi+t, LXmi-t, Xmi)
    xma = max(RXma+t, LXma-t, Xma)
    ymi = min(UYmi+t, DYmi-t, Ymi)
    yma = max(UYma+t, DYma-t, Yma)
    return max(yma-ymi, 0)*max(xma-xmi, 0)
    
def dii(t):
    a = Decimal("0.00000001")
    return calc(t+a) - calc(t-a)

l = Decimal("0")
r = Decimal("10000000000")
for _ in range(500):
    m = (l+r)/2
    if dii(m) > 0:
        r = m
    else:
        l = m
print(calc(m))
### BUGGY CODE ###

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

li = [input() for i in range(q)]

k= 0

for i in range(q):
    if li[i] == "1":
        k += 1
    else:
        li3 = li[i].split()
        if (int(li3[1])+k) % 2 == 0:
            s = s + li3[2]
        else:
            s = li3[2] + s

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

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())

li = [input() for i in range(q)]
k = 0
ans = [s]
ans = deque(ans)

for i in li:
    if i == "1":
        k += 1
    else:
        if (int(i[2]) + k) % 2 == 0:
            ans.append(i[4])
        else:
            ans.appendleft(i[4])

ans = list(ans)
s = "".join(ans)
if k % 2 == 0:
    print(s)
else:
    print(s[::-1])
### BUGGY CODE ###

N = int(input())
S = input()

diff_dic = {}
diff_dic[('R', 'G')] = []
diff_dic[('R', 'B')] = []
diff_dic[('G', 'R')] = []
diff_dic[('G', 'B')] = []
diff_dic[('B', 'G')] = []
diff_dic[('B', 'R')] = []

R_lst = [0] * N
G_lst = [0] * N
B_lst = [0] * N

r_cnt = 0
g_cnt = 0
b_cnt = 0

cnt = 0
for i in range(N):
    if S[i] == 'R':
        r_cnt += 1
    elif S[i] == 'G':
        g_cnt += 1
    else:
        b_cnt += 1

    R_lst[i] = r_cnt
    G_lst[i] = g_cnt
    B_lst[i] = b_cnt

    for j in range(i):
        d = i - j
        if (S[i] == 'R' and S[j] == 'G') or (S[i] == 'G' and S[j] == 'R'):
            if j - 1 >=0 and B_lst[j - 1] > 0:
                cnt += B_lst[j - 1]
                if j - d >= 0 and S[j - d] == 'B':
                    cnt -= 1

        if (S[i] == 'G' and S[j] == 'B') or (S[i] == 'B' and S[j] == 'G'):
            if j - 1 >=0 and R_lst[j - 1] > 0:
                cnt += R_lst[j - 1]
                if j - d >= 0 and S[j - d] == 'R':
                    cnt -= 1

        if (S[i] == 'B' and S[j] == 'R') or (S[i] == 'R' and S[j] == 'B'):
            if j - 1 >= 0 and G_lst[j - 1] > 0:
                cnt += G_lst[j - 1]
                if j - d >= 0 and S[j - d] == 'G':
                    cnt -= 1

print(cnt)


### FIXED CODE ###

N = int(input())
S = input()

diff_dic = {}
diff_dic[('R', 'G')] = []
diff_dic[('R', 'B')] = []
diff_dic[('G', 'R')] = []
diff_dic[('G', 'B')] = []
diff_dic[('B', 'G')] = []
diff_dic[('B', 'R')] = []

R_lst = [0] * N
G_lst = [0] * N
B_lst = [0] * N

r_cnt = 0
g_cnt = 0
b_cnt = 0

cnt = 0
for i in range(N):
    if S[i] == 'R':
        r_cnt += 1
    elif S[i] == 'G':
        g_cnt += 1
    else:
        b_cnt += 1

    R_lst[i] = r_cnt
    G_lst[i] = g_cnt
    B_lst[i] = b_cnt

    for j in range(i):
        d = i - j
        if (S[i] == 'R' and S[j] == 'G') or (S[i] == 'G' and S[j] == 'R'):
            if j - 1 >=0 and B_lst[j - 1] > 0:
                cnt += B_lst[j - 1]
                if j - d >= 0 and S[j - d] == 'B':
                    cnt -= 1

        if (S[i] == 'G' and S[j] == 'B') or (S[i] == 'B' and S[j] == 'G'):
            if j - 1 >=0 and R_lst[j - 1] > 0:
                cnt += R_lst[j - 1]
                if j - d >= 0 and S[j - d] == 'R':
                    cnt -= 1

        if (S[i] == 'B' and S[j] == 'R') or (S[i] == 'R' and S[j] == 'B'):
            if j - 1 >= 0 and G_lst[j - 1] > 0:
                cnt += G_lst[j - 1]
                if j - d >= 0 and S[j - d] == 'G':
                    cnt -= 1

print(cnt)
### BUGGY CODE ###

import fractions as mt
from functools import reduce
def gcd(nums):
    return reduce(mt.gcd, nums)
N = int(input())
A = list(map(int, input().split()))
g = []
for i in range(N):
    g.append(gcd(A[:i]+A[i+1:]))
print(max(g))

### FIXED CODE ###

class SegmentTree:
    def __init__(self, seq, func="min"):
        if func=="min":
            self.f = min
            self.e = float('inf')
        if func=="max":
            self.f = max
            self.e = -float('inf')
        if func=="gcd":
            self.f = gcd
            self.e = 0
        self._n = len(seq)
        self.n_seg = 2**(self._n-1).bit_length()
        self.seg = [self.e]*2*self.n_seg
        
        for i in range(self._n):
            self.seg[self.n_seg+i-1] = seq[i]
            
        for i in range(self.n_seg-2, -1, -1):
            self.seg[i] = self.f(self.seg[2*i+1], self.seg[2*i+2])
        
    def update(k, val):
        k += self.n_seg -1
        self.seg[k] = val
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.f(self.seg[k*2+1], self.seg[k*2+2])
        
    def query(self, a, b):
        if b<=a:
            return self.e
        a += self.n_seg-1
        b += self.n_seg-2
        res = self.e
        while b-a>1:
            if a&1==0:
                res = self.f(res, self.seg[a])
            if b&1==1:
                res = self.f(res, self.seg[b])
                b -= 1
            a = a//2
            b = (b-1)//2
        if a==b:
            res = self.f(res, self.seg[a])
        else:
            res = self.f(self.f(res, self.seg[a]), self.seg[b])
        return res
    
    def __repr__(self):
        ret = str(self.seg[self._n-1:])
        return ret

def gcd(a, b):
    if b>a:
        a, b = b, a
    while b:
        a, b = b, a%b
    return a

if __name__=="__main__":
    N = int(input())
    A = list(map(int, input().split()))
    A_seg = SegmentTree(A, func="gcd")
    ans = -1
    for i in range(N):
        ans = max(ans, gcd(A_seg.query(0, i), A_seg.query(i+1, N)))
    print(ans)
### BUGGY CODE ###

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

BC = []
for _ in range(M):
    b, c = map(int, input().split())
    BC.append((b, c))
    
cards = A[:]
#cards  =sorted(cards)

opes = BC[:]
#opes = sorted(opes, reverse=True, key=lambda x: x[1])

#print(cards)
#print(opes)

top_list = []
for b, c in opes:
    top_list += [c] * b
    
cards = cards + top_list
cards = sorted(cards, reverse=True)

ans = sum(cards[:N])
print(ans)
    

            


### FIXED CODE ###

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

BC = []
for _ in range(M):
    b, c = map(int, input().split())
    BC.append((b, c))
    
cards = A[:]
opes = BC[:]

cards_dict = {}

for c in cards:
    if c in cards_dict:
        cards_dict[c] += 1
    else:
        cards_dict[c] = 1

for b, c in opes:
    if c in cards_dict:
        cards_dict[c] += b
    else:
        cards_dict[c] = b
        
cards_dict = sorted(cards_dict.items(), reverse=True)
#print(cards_dict)

num = 0
ans = 0
for k, v in cards_dict:
    if num + v > N:
        ans += k * (N-num)
        num = N
    else:
        ans +=  k * v
        num += v
    if num == N:
        break
        
print(ans)
### BUGGY CODE ###

def main():
  import sys
  sys.setrecursionlimit(10**7)
  N,W=list(map(int,sys.stdin.readline().split()))

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

  WL=[0]* N
  VL=[0]*N

  for i in range(N):
      w,v=list(map(int,sys.stdin.readline().split()))
      WL[i]=w
      VL[i]=v


  def dfs(W,i):
      if i==N:
          return 0
      if dp[W][i]:
          return dp[W][i]
      if W-WL[i]>=0:
          dp[W][i]=max(dfs(W,i+1),dfs(W-WL[i],i+1)+VL[i])
          return dp[W][i]
      else:
          dp[W][i]=dfs(W,i+1)
          return dp[W][i]

  print(dfs(W,0))

main()


### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**7)
    N,W=list(map(int,sys.stdin.readline().split()))

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

    WL=[0]*N
    VL=[0]*N

    for i in range(N):
        w,v=list(map(int,sys.stdin.readline().split()))
        WL[i]=w
        VL[i]=v

    for i in range(1,N+1):
        for w in range(1,W+1):
            if w>=WL[i-1]:
                a=dp[i-1][w-WL[i-1]]+VL[i-1]
                b=dp[i-1][w]
                dp[i][w]=max(a,b)
            else:
                dp[i][w]=dp[i-1][w]
    print(dp[-1][-1])
main()
### BUGGY CODE ###

# get initial input parameter
n, k, q = map(int, input().split())

# get answer list
answer_list = [ int(input()) for _ in range(q) ]

# init correct num list
correct_num_list = [ answer_list.count(answer + 1) for answer in range(n) ]

for answer in range(n):
    if (0 < (k - (q - correct_num_list[answer]))):
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

# get initial input parameter
n, k, q = map(int, input().split())
 
# init point
point_list = [ (k - q) for _ in range(n) ]
 
for round in range(q):
    # get correct answer persion
    person_index = int(input()) - 1
    
    # point decrement
    point_list[person_index] += 1
 
for item in point_list:
    if (0 < item):
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n, m = list(map(int, input().split()))
l = []
r = []
for i in range(m):
    x, y=[int(i) for i in input().split()]
    l.append(x)
    r.append(y)
ans = 0
for i in range(n):
    cnt = 0
    #print('i=' + str(i))
    for j in range(m):
        #print(l[j], end=' ')
        #print(r[j])
        if i + 1 < l[j] or r[j] < i + 1:
            pass
        else:
            cnt += 1
            #print('cnt='+ str(cnt))
    if cnt == m:
        ans += 1
print(ans)


### FIXED CODE ###

n, m = list(map(int, input().split()))
maxl = 0
minr = 1000000
for i in range(m):
    l, r = list(map(int, input().split()))
    maxl = max(maxl, l)
    minr = min(minr, r)
if minr < maxl:
    print(0)
else:
    print(minr - maxl + 1)
### BUGGY CODE ###

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

### FIXED CODE ###

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

from scipy.misc import comb
from collections import defaultdict
d = defaultdict(lambda: -1)
n = int(input())
a = [int(x) for x in input().split()]
ans = 0
for i in range(len(a)):
  a_ = a.copy()
  b = a_.pop(i)
  if d[str(b)] != -1:
    print(d[str(b)])
    continue
  A = list(set(a_))
  ans = 0
  for j in A:
    ans += comb(a_.count(j), 2, exact=True)

  d[str(b)] = ans
  print(ans)


### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
from collections import defaultdict
d = defaultdict(int)
for i in a:
  d[i] += 1

total = 0
for i in set(a):
  x = d[i]
  total += x*(x-1)/2

for i in a:
  x = d[i]
  print(int(total-((x*(x-1)/2))+((x-1)*(x-2)/2)))
### BUGGY CODE ###

a = int(input())
b = list(map(int,input().split()))
c  = 1
for i in range(0,a):
    c *= b[i]
if c > 10**18 :
    print(-1)
else :
    print(c)


### FIXED CODE ###

a = int(input())
b = list(map(int,input().split()))
b.sort()
c  = 1
yon = 10**18
for i in b:
    c *= i
    if c > yon :
     print(-1)
     exit()
print(c)
### BUGGY CODE ###

K=input()
keta = len(K)
k=int(K)
if k%2==0:
  print(-1)
else:
  seven = "7"*keta
  s = int(seven)
  ans=keta-1
  while (1):
    ans+=1
    s = s%k
    if s==0:
      print(ans)
      break
    else:
      s = s*10+7


### FIXED CODE ###

k=int(input())
if k%2==0 or k%5==0:
  print(-1)
else:
  s=7
  for i in range(k):
    if s%k==0:
      print(i+1)
      exit()
    else:
      s=(s*10+7)%k
### BUGGY CODE ###

import numpy as np
n=int(input())
p=np.array(list(map(int, input().split())))

cnt = 0
for i,v in enumerate(p):
    if i == 0:
        cnt += 1
        continue
    if np.min(p[:i]) > v:
        cnt += 1
print(cnt)

### FIXED CODE ###

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

cnt = 0
for i,v in enumerate(p):
    if i == 0:
        cnt += 1
        min_ = v
        continue
    if min_ > v:
        min_ = v
        cnt += 1
print(cnt)