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

n, w = list(map(int, input().strip().split()))
data = []
for i in range(n):
    data.append(list(map(int, input().strip().split())))

dp = {}

# i 個までで重さを z 以下にしたときの最大値
def rec(i, z):
    if (i, z) in dp:
        return dp[(i, z)]

    if i < 0:
        ret = 0
    # i 個目のものを入れられない場合
    elif data[i][0] > z:
        ret = rec(i - 1, z)
    else:
        # 入れられる場合、入れるときと入れないときのうち大きい方を返す
        # 入れるとき
        v1 = data[i][1] + rec(i - 1, z - data[i][0])
        # 入れないとき
        v2 = rec(i - 1, z)
        ret = max(v1, v2)
        dp[(i, z)] = ret
    return ret

print(rec(n - 1, w))

### FIXED CODE ###

n, w = map(int, input().strip().split())
data = [list(map(int, input().strip().split())) for _ in range(n)]

# i番目に重さがj以下となるように選んだときの価値の総和の最大値
dp = [[0] * (w + 1) for _ in range(n)]

for i in range(0, n):
    for j in range(w + 1):
        # i 番目の品物の重さと価値
        wi, vi = data[i]
        if i == 0:
            take = vi if j - wi >= 0 else 0
            miss = 0
            dp[i][j] = max(take, miss)
        else:
            # i番目の品物を入れる場合
            take = dp[i - 1][j - wi] + vi if j - wi >= 0 else 0
            # 入れない場合
            miss = dp[i - 1][j]
            dp[i][j] = max(take, miss)

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

n=int(input())
l=[list(map(int,input().split()))+[i] for i in range(n-1)]
l.sort()
#print(l)
aa=[[] for _ in range(n)]
#aa[l[0][0]-1].append(1)
def bfs(v):
    d=[-1]*n
    d[v]=0
    q=[v]
    c=1
    #print(d,q)
    while q:
        q1=[]
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
                    for k in range(1,n):
                        if k not in set(aa[i]) and k not in set(aa[j]):
                            aa[j].append(k)
                            aa[i].append(k)
                            break
        q=q1
        c+=1
        #print(aa,d,q)
    return d


pt=[[] for _ in range(n)]
for i in range(n-1):
    pt[l[i][0]-1].append(l[i][1]-1)
    pt[l[i][1]-1].append(l[i][0]-1)
#print(pt)
ans=bfs(l[0][0]-1)
#print(aa)
A=0
for i in range(n):
    A=max(A,max(aa[i]))
print(A)
for i in range(n-1):
    #print(aa)
    #print(aa[l[i][0]-1][0])
    l[i].append(aa[l[i][0]-1][0])
    aa[l[i][0]-1]=aa[l[i][0]-1][1:]
    aa[l[i][1]-1]=aa[l[i][1]-1][1:]
l=sorted(l, key=lambda x: x[2])
for i in range(n-1):
    print(l[i][3])


### FIXED CODE ###

n = int(input())
l=[list(map(int,input().split()))+[i+1] for i in range(n-1)]
l.sort()
flg = [0 for _ in range(n+1)]
ans = [0 for _ in range(n)]
#print(l)
t=0
count=0
for i in range(n-1):
    a,b,c=l[i]
    if t!=a:
        t=a
        count=1
    if flg[a]==count:
        count+=1
    flg[b]=count
    ans[c]=count
    count+=1
    #print(flg,ans)
print(max(flg))
for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###

# encoding:utf-8
import copy
import numpy as np
import random

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

A.sort()
B.sort()
C.sort()

step2 = [0 for i in range(N)]
for j in range(N):
    maxim_value = 0
    for i in range(maxim_value,N):
        if A[i] >= B[j]:
            step2[j] = i
            maxim_value = i
            break
        elif i == N-1:
            step2[j] = i+1
            maxim_value = i+1

ans = 0
for i in range(N):
    mini_value = 0
    for j in range(mini_value,N):
        if B[i] < C[j]:
            mini_value = j
            ans += step2[i]*(N-j)
            break
# print(step2)

print(ans)


### FIXED CODE ###

# encoding:utf-8
import copy
import numpy as np
import random
import time
import bisect

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

A.sort()
B.sort()
C.sort()

sum = 0

for i in range(N):
    a = bisect.bisect_left(A,B[i])

    c = N-bisect.bisect_right(C,B[i])
    # print(a,c)

    sum += a*c

print(sum)
### BUGGY CODE ###

n = 10**7+1
P = [1 for _ in range(n)]
P[0]=0
P[1]=0
for i in range(2,int(n**0.5)+1):
    for j in range(i*i,n,i):
        P[j] = 0
Q = []
for i in range(2,n):
    if P[i]==1:
        Q.append(i)
def f(x):
    if x==1:
        return 1
    if P[x]==1:
        return 2
    C = {}
    for q in Q:
        if x%q==0:
            cnt = 0
            while x%q==0:
                x = x//q
                cnt += 1
            C[q] = cnt
        if x==1:break
        if P[x]==1:
            C[x]=1
            break
    num = 1
    for q in C:
        num *= C[q]+1
    return num
N = int(input())
cnt = 0
for i in range(1,N+1):
    cnt += i*f(i)
print(cnt)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1,N+1):
    for j in range(i,N+1,i):
        ans += j
print(ans)
### BUGGY CODE ###

def main():
    n=int(input())
    s=input()
    r = [0]*n
    g = [0]*n
    b = [0]*n
    ans = 1

    dict = {"R":r, "G":g, "B":b}

    for i in range(n):
        dict[s[i]][i] = 1
    
    ans = sum(dict["R"])*sum(dict["G"])*sum(dict["B"])
 
    for i in range(n):
        for j in range(i,n):
            s1 = s[i]
            s2 = s[j]
            if s1 != s2:
                t = (s1,s2)
                for s3 in "RGB":
                    if s3 not in t:
                        if 2*j-i < n and dict[s3][2*j-i] == 1:
                            ans -= 1
                        continue

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n=int(input())
    s=input()
    ans = 1

    r_cnt = s.count("R")
    g_cnt = s.count("G")

    ans = r_cnt*g_cnt*(n-r_cnt-g_cnt)
 
    for i in range(n):
        for j in range(i,n):
            s1 = s[i]
            s2 = s[j]
            if s1 != s2:
                t = (s1,s2)
                for s3 in "RGB":
                    if s3 not in t:
                        if 2*j-i < n and s[2*j-i] == s3:
                            ans -= 1
                        continue

    print(ans)

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

import re

s = input()
n = len(s)
k = int(input())
l = []
for i in range(26):
  m_list = [m.start() for m in re.finditer(chr(ord('a')+i), s)]
  #print(m_list)
  
  for start in m_list:
    c=1
    while start + c <= n:
      if not s[start:start+c] in l:
        l.append(s[start:start+c])
      c += 1
  if len(l) >= k:
    break
#print(l)
print(sorted(l)[k-1])
    


### FIXED CODE ###

import re

s = input()
n = len(s)
k = int(input())
l = []
for i in range(26):
  m_list = [m.start() for m in re.finditer(chr(ord('a')+i), s)]
  #print(m_list)
  
  for start in m_list:
    c=1
    while start + c <= n and c <= 5:
      if not s[start:start+c] in l:
        l.append(s[start:start+c])
      c += 1
  if len(l) >= k:
    break
#print(l)
print(sorted(l)[k-1])
### BUGGY CODE ###

import copy
N = int(input())
X = [int(x) for x in input().split()]
Y = copy.copy(X)
X.sort()
Z = copy.copy(X)
#print(Y,Z)
center = (N -2) // 2

for i in range(0,N):
    X.remove(Y[i])
    #print(X)
    print(X[center])
    X = copy.copy(Z)
    #print(X)

### FIXED CODE ###

import copy
N = int(input())
X = [int(x) for x in input().split()]
Y = copy.copy(X)
X.sort()  #ソートした

for i in range(0,N):
    if Y[i] <= X[(N // 2) -1]:
        print(X[(N // 2)])
    else:
        print(X[(N // 2)-1])
### BUGGY CODE ###

#

import sys
input=sys.stdin.readline
MOD=10**9+7

def main():
    H,N=map(int,input().split())
    AB=[list(map(int,input().split())) for i in range(N)]
    dp=[10**9]*(H+1+10**4)
    dp[0]=0
    for i in range(H+10**4):
        for j in range(N):
            if 0<=i+AB[j][0]<=H+10**4:
                dp[i+AB[j][0]]=min(dp[i+AB[j][0]],dp[i]+AB[j][1])
    ans=10**9
    for i in range(H,H+1+10**4):
        ans=min(ans,dp[i])
    print(ans)
    
        
    
if __name__=="__main__":
    main()


### FIXED CODE ###

#

import sys
input=sys.stdin.readline
MOD=10**9+7

def main():
    H,N=map(int,input().split())
    AB=[list(map(int,input().split())) for i in range(N)]
    dp=[10**9]*(H+1+10**4)
    dp[0]=0
    for i in range(H+10**4):
        for j in range(N):
            if 0<=i+AB[j][0]<=H+10**4:
                dp[i+AB[j][0]]=min(dp[i+AB[j][0]],dp[i]+AB[j][1])
    ans=10**9
    for i in range(H,H+1+10**4):
        ans=min(ans,dp[i])
    print(ans)
    
        
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

S = input()
A,B,C,Q = [], [], [], []
for i, s in enumerate(S):
    if s == 'A':
        A.append(i)
    elif s == 'B':
        B.append(i)
    elif s == 'C':
        C.append(i)
    else:
        Q.append(i)

import bisect
ans = 0
for b in B + Q:
    ai = bisect.bisect_left(A, b)
    qa = bisect.bisect_left(Q, b)
    a = ai * (3 ** qa)
    if qa > 0:
        a += 3 ** (qa - 1) * qa

    ci = bisect.bisect_right(C, b)
    qc = bisect.bisect_right(Q, b)
    lc = len(C) - ci
    lqc = len(Q) - qc
    c = lc * (3 ** lqc)
    if lqc > 0:
        c += 3 ** (lqc - 1) * lqc
    
    ans += a * c

print(ans % (10**9 + 7))

### FIXED CODE ###

S = input()
n = len(S)
mod = (10**9 + 7)

dp = [[0] * 4 for _ in range(n + 1)]

dp[n] = [0, 0, 0, 1]
for i in range(n-1, -1, -1):
    if S[i] == '?':
        dp[i][3] =  dp[i+1][3] * 3 % mod
        dp[i][2] = (dp[i+1][2] * 3 + dp[i+1][3]) % mod
        dp[i][1] = (dp[i+1][1] * 3 + dp[i+1][2]) % mod
        dp[i][0] = (dp[i+1][0] * 3 + dp[i+1][1]) % mod
    elif S[i] == 'C':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] = (dp[i+1][2] + dp[i+1][3]) % mod
        dp[i][1] =  dp[i+1][1] % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'B':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] =  dp[i+1][2] % mod
        dp[i][1] = (dp[i+1][1] + dp[i+1][2]) % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'A':
        dp[i][3] =  dp[i+1][3]
        dp[i][2] =  dp[i+1][2]
        dp[i][1] =  dp[i+1][1]
        dp[i][0] = (dp[i+1][0] + dp[i+1][1]) % mod
print(dp[0][0])
### BUGGY CODE ###

N = int(input())
S = []
c = 0
for i in range(N):
	j = input()
	if not j in S:
		S.append(j)
		c += 1
print(c)




### FIXED CODE ###

N = int(input())
S = []
c = 0
for i in range(N):
	S.append(input())

S = list(set(S))
print(len(S))
### BUGGY CODE ###

def solve(string):
    a, b = map(int, string.split())
    tmp = a
    for i in range(a + 1, b + 1):
        tmp ^= i
    return str(tmp)


if __name__ == '__main__':
    print(solve(input()))


### FIXED CODE ###

def solve(string):
    a, b = map(int, string.split())
    if b == 0:
        return "0"
    bin_a = "{:040b}".format(a)
    bin_b = "{:040b}".format(b)
    aa = [-1 if _a == "0" else int(bin_a[i + 1:] or "0", 2) for i, _a in enumerate(bin_a)]
    bb = [-1 if _b == "0" else int(bin_b[i + 1:] or "0", 2) for i, _b in enumerate(bin_b)]
    index = 0
    while True:
        if bb[index] != -1:
            break
        index += 1
    ans = []
    while index < 40:
        if aa[index] == bb[index] == -1:
            ans.append("0")
        elif aa[index] == -1:
            ans.append(str((bb[index] + 1) % 2))
        elif bb[index] == -1:
            ans.append(str(aa[index] % 2))
        else:
            ans.append(str((bb[index] + 1 - aa[index]) % 2))
        index += 1
    ans[-1] = str((b - a) // 2 % 2) if a % 2 == b % 2 == 0 else str(((b - a) // 2 + 1) % 2)
    return str(int("".join(ans), 2))


if __name__ == '__main__':
    print(solve(input()))
### BUGGY CODE ###

import itertools
N = int(input())
S = [input() for i in range(N)]
candi = []
for s in S:
    if s[0] == 'M' or s[0] == 'A' or s[0] == 'R' or s[0] == 'C' or s[0] == 'H':
        candi.append(s)
combi = list(itertools.combinations(candi,3))
counter  = 0
for i in combi:
    if i[0][0] != i[1][0] and  i[1][0] != i[2][0] and  i[0][0] != i[2][0]:
        counter += 1
print(counter)


### FIXED CODE ###

import itertools
import collections
N = int(input())
S = [input() for i in range(N)]
candi = []
for s in S:
    if s[0] == 'M' or s[0] == 'A' or s[0] == 'R' or s[0] == 'C' or s[0] == 'H':
        candi.append(s[0])
col_s = collections.Counter(candi)
combi_s = itertools.combinations(list(col_s),3)
counter = 0 
for i in combi_s:
    counter += col_s[i[0]]*col_s[i[1]]*col_s[i[2]]
print(counter)
### BUGGY CODE ###

import functools
import operator
n = int(input())
A = list(map(int, input().split()))
ans = functools.reduce(operator.mul, A)

print(ans if ans <= 10**18 else '-1')

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 1
if min(A) == 0:
    ans = 0
else:
    for a in A:
        ans *= a
        if ans > 10 ** 18:
            ans = '-1'
            break


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

def solve(i, m, A, n):
  if m == 0:
    return 1
  if i >= n:
    return 0
  res = solve(i+1, m, A, n) or solve(i+1, m-A[i], A, n)
  return res


n = input()
A = map(int, raw_input().split())
p = input()
m = map(int, raw_input().split())
for i in range(p):
  if solve(0, m[i], A, n):
    print 'yes'
  else:
    print 'no'

### FIXED CODE ###

def solve(i, m):
  if dp[i][m] != -1:
    return dp[i][m]

  if m == 0:
    dp[i][m] = 1
  elif i >= n:
    dp[i][m] = 0
  elif solve(i+1, m):
    dp[i][m] = 1
  elif solve(i+1, m-A[i]):
    dp[i][m] = 1
  else:
    dp[i][m] = 0

  return dp[i][m]



n = input()
A = map(int, raw_input().split())
p = input()
m = map(int, raw_input().split())

dp = [[-1 for col in range(2000)] for row in range(n+1)]

for i in range(p):
  if solve(0, m[i]):
    print 'yes'
  else:
    print 'no'
### BUGGY CODE ###

import sys

input = sys.stdin.readline

N, K = map(int, input().split())
diff = abs(K - N)

if N % K == 0:
    print(0)
    exit()
while True:
    if diff < abs(diff - K):
        break
    else:
        diff = abs(K - diff)
print(diff)

### FIXED CODE ###

import sys

input = sys.stdin.readline

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

if N < K:
    print(min(N, K - N))
    exit()

if N % K == 0:
    print(0)
else:
    print(min(K - N%K, N%K))
### BUGGY CODE ###

n = int(input())
ans = float('inf')
temp = 0
for i in range(1,(n//2)+2):
    if n%i == 0:
        temp = max(len(str(i)), len(str(n//i)))
        ans = min(temp, ans)
print(ans)

### FIXED CODE ###

n = int(input())
ans = float('inf')
temp = 0
for i in range(int(n**(1/2)), 0, -1):
    if n%i == 0:
        temp = max(i, n//i)
        ans = min(temp, ans)
print(len(str(ans)))
### BUGGY CODE ###

import math
def comb(x,y):
    f = 1
    for i in range(y):
        f *= (x-i)
        f //= (i+1)

    return f

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

cnt = [0]
for i in range(2,m+1):
    while m!=i:
        if m%i==0:
            m //=i
            cnt[-1]+=1
        else:
            cnt.append(0)
            break
    if m==i:
        cnt[-1]+=1
        break
cnt = [item for item in cnt if cnt != 0]


res = 1

for item in cnt:
    res *= comb(item+n-1,n-1)

print(res%(10**9+7))


### FIXED CODE ###

import math
def comb(x,y):
    f = 1
    for i in range(y):
        f *= (x-i)
        f //= (i+1)

    return f

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

i = 2
cnt = []
while i*i<=m:
    c = 0
    while m%i == 0:
        m //= i
        c += 1
    if c>0:
        cnt.append(c)
    i+=1
if m>1:
    cnt.append(1)
        

res = 1
r = 10**9 +7
for item in cnt:
    res = (res* comb(item+n-1,item))%r

print(res%r)
### BUGGY CODE ###

x,y,a,b,c = map(int,raw_input().split(' '))

aas = map(int, raw_input().split(' '))
bbs = map(int, raw_input().split(' '))
ccs = map(int, raw_input().split(' '))
aas.sort(key = lambda x:-x)
bbs.sort(key = lambda x:-x)
ccs.sort(key = lambda x:-x)

for i in range(1,len(aas)): aas[i] += aas[i-1]
for i in range(1,len(bbs)): bbs[i] += bbs[i-1]
for i in range(1,len(ccs)): ccs[i] += ccs[i-1]


r = 0
for a in range(x+1):
	for b in range(y+1):
		m = (aas[a-1] if a-1 >= 0 else 0) + (bbs[b-1] if b-1 >=0 else 0)
		c = x + y - (a + b)
		if c > 0 and c-1 < len(ccs): 	 	
			m += ccs[c-1]
		else: 
			if c: m+= -float('inf')

		r = max(r, m)

print r


### FIXED CODE ###

import collections
x,y,aa,bb,cc = map(int,raw_input().split(' '))

aas = map(int, raw_input().split(' '))
bbs = map(int, raw_input().split(' '))
ccs = map(int, raw_input().split(' '))

aas.sort(key = lambda x:-x)
bbs.sort(key = lambda x:-x)
ccs.sort(key = lambda x:-x)
aas = aas[:x]
bbs = bbs[:y]

r = (aas + bbs)
r.sort()

i = 0
j = 0
while(j < len(ccs) and i < len(r)):
	if ccs[j] > r[i]:
		r[i] = ccs[j]
		i+=1
	j+=1

print sum(r)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 1000000007
res = 0

for i in range(n - 1):
    main = a.pop(0)
    res =  (res + main * sum(a) % mod) % mod
print(res)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 1000000007
res = 0
a_sum = sum(a)

for i in range(n - 1):
    main = a[i]
    a_sum = a_sum - main
    res =  (res + main * a_sum % mod) % mod
print(res)
### BUGGY CODE ###

def main():
    N,K=map(int,open(0).read().split())
    keta=1
    flag=0
    A=K
    while flag==0:
        if A<=N and A*K>N:
            print(keta+1)
            return
        A*=K
        keta= keta+1
main()

### FIXED CODE ###

def Base_10_to_n(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out
    
def main():
    N,K=map(int,input().split())
    print(len(Base_10_to_n(N,K)))
main()
### BUGGY CODE ###

N = int(input())
A = [0]
A.extend(list(map(int, input().split())))

buka_num = []

for i in range(1,N):
    tmp_A = A[i:]
    buka_num.append(tmp_A.count(i))
    
buka_num.append(0)
for ele in buka_num:
    print(ele)

### FIXED CODE ###

import collections
N = int(input())
A = [0]
A.extend(list(map(int, input().split())))
c = collections.Counter(A)
buka_num = []

for i in range(1,N):
    buka_num.append(c[i])
    
buka_num.append(0)
for ele in buka_num:
    print(ele)
### BUGGY CODE ###

N, M = map(int, input().split())
mod = 10**9 + 7
# 一個数列が決まった場合に、その数列と同じ数字が同じ場所にあるものが禁止される。


ans = M
for i in range(M-1, M-N, -1):
    ans = ans*i % mod


# print(ans)
prev = 1
ansB = M-1

for i in range(1, N):
    tmp = (prev)*i

    tmp2 = ansB - tmp
    # print(tmp2)

    ansB = tmp * (M-i) + (tmp2)*(M-i-1)
    # print(tmp, tmp2)
    # ansB = tmp + tmp2
    ansB %= mod
    prev = tmp2
    # print(ansB)
# print(ansB)

print((ans*ansB) % mod)


### FIXED CODE ###

N, M = map(int, input().split())
mod = 10**9 + 7

ans = M
for i in range(M-1, M-N, -1):
    ans = ans*i % mod


# print(ans)
prev = 1
ansB = M-1


for i in range(1, N):
    tmp = (prev)*i % mod
    tmp2 = ansB - tmp % mod
    # print(tmp2)
    ansB = tmp * (M-i) % mod
    ansB += (tmp2)*(M-i-1) % mod
    # print(tmp, tmp2)
    # ansB = tmp + tmp2
    ansB %= mod
    prev = tmp2
    # print(ansB)

# print(ansB)

print((ans*ansB) % mod)
### BUGGY CODE ###

# C - Go to School
def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = []
    for i in range(1, n+1):
        ans.append(a.index(i) + 1)
    print(" ".join(map(str, ans)))
    
if __name__ ==  "__main__":
    main()

### FIXED CODE ###

# C - Go to School
def main():
    import numpy as np
    n = int(input())
    a = list(map(int, input().split()))
    a = np.array(a)
    a = np.argsort(a)
    for i in a:
        print(i+1,end=" ")

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

import sys
import math
from functools import reduce


def main():
    input = sys.stdin.readline
    K = int(input())
    assert 1 <= K <= 200
    total = 0
    for i in range(1, K+1):
        for j in range(1, K+1):
            for k in range(1, K+1):
                total += gcd_list([i, j, k])
    print(total)


def gcd_list(numbers):
    return reduce(euclidean_algorithm, numbers)


def euclidean_algorithm(a, b):
    r = a % b
    while r != 0:
        a = b
        b = r
        r = a % b
    return b


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import math
from functools import reduce


def main():
    input = sys.stdin.readline
    K = int(input())
    assert 1 <= K <= 200
    total = 0
    for i in range(1, K+1):
        for j in range(1, K+1):
            a = euclidean_algorithm(i, j)
            for k in range(1, K+1):
                total += euclidean_algorithm(a, k)
    print(total)


def gcd_list(numbers):
    return reduce(euclidean_algorithm, numbers)


def euclidean_algorithm(a, b):
    r = a % b
    while r != 0:
        a = b
        b = r
        r = a % b
    return b


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

[R, C, K] = list(map(int, input().split()))
G = [[None]*C for i in range(R)]
for i in range(K):
    [r, c, v] = list(map(int, input().split()))
    G[r-1][c-1] = v

dp = [[[-1]*4 for i in range(C)] for j in range(R)]
dp[0][0][0] = 0
if G[0][0] != None:
    dp[0][0][1] = G[0][0]

for r in range(R):
    for c in range(C):
        for k in range(4):
            if dp[r][c][k] == -1: continue

            if c+1<C and G[r][c+1] != None and k < 3: # can go right and pick up
                dp[r][c+1][k+1] = max(dp[r][c+1][k+1], dp[r][c][k] + G[r][c+1])
            if c+1<C: # moving right without picking up
                dp[r][c+1][k] = max(dp[r][c+1][k], dp[r][c][k])
            if r+1<R: # moving downward without picking up
                dp[r+1][c][0] = max(dp[r+1][c][0], dp[r][c][k])
            if r+1<R and G[r+1][c] != None: # can go right and pick up
                dp[r+1][c][1] = max(dp[r+1][c][1], dp[r][c][k] + G[r+1][c])

print(max(dp[r][c]))


### FIXED CODE ###

import numpy as np
from numba import jit

R, C, K = map(int, input().split())
G = np.zeros((R+1, C+1), np.int64)
for i in range(K):
    [r, c, v] = list(map(int, input().split()))
    G[r-1][c-1] = v

@jit
def main(G, R, C):
    dp = np.full((R+1, C+1, 4), -1)
    dp[0][0][0] = 0
    if G[0][0] != None: dp[0][0][1] = G[0][0]
    for r in range(R):
        for c in range(C):
            for k in range(4):
                if dp[r][c][k] == -1: continue
                if k < 3: # can go right and pick up
                    if dp[r][c+1][k+1] < dp[r][c][k] + G[r][c+1]:
                        dp[r][c+1][k+1] = dp[r][c][k] + G[r][c+1]
                if dp[r][c+1][k] < dp[r][c][k]:
                    dp[r][c+1][k] = dp[r][c][k]
                if dp[r+1][c][0] < dp[r][c][k]:
                    dp[r+1][c][0] = dp[r][c][k]
                if dp[r+1][c][1] < dp[r][c][k] + G[r+1][c]:
                    dp[r+1][c][1] = dp[r][c][k] + G[r+1][c]
    return(max(dp[r][c]))

ret = main(G, R, C)
print(ret)
### BUGGY CODE ###

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

P = 998244353

fact = [1]
for i in range(1, 300010):
  fact.append(fact[i-1] * i % P)

def egcd(a, b):
  if b == 0:
    return a, 1, 0
  else:
    q, r = divmod(a, b)
    g, x, y = egcd(b, r)
    return g, y, x - q * y

def inv(n):
  g, x, _ = egcd(n, P)
  # assert g == 1
  return x

def comb(n, k):
  # assert 0 <= k <= n
  return fact[n] * inv(fact[k]) % P * inv(fact[n-k]) % P

N, A, B, K = reads()

result = 0
for x in range(N+1):
  y, r = divmod(K - A * x, B)
  if r == 0 and 0 <= y <= N:
    result = (result + comb(N, x) * comb(N, y) % P) % P

print(result)

### FIXED CODE ###

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

P = 998244353

N, A, B, K = reads()

def inv(n):
  return pow(n, P-2, P)

fact = [1] * (N+1)
for i in range(1, N+1):
  fact[i] = fact[i-1] * i % P

invfact = [inv(fact[N])] * (N+1)
for i in range(N, 0, -1):
  invfact[i-1] = invfact[i] * i % P

def comb(n, k):
  # assert 0 <= k <= n
  return fact[n] * invfact[k] * invfact[n-k] % P

result = 0
for x in range(N+1):
  y, r = divmod(K - A * x, B)
  if r == 0 and 0 <= y <= N:
    result = result + comb(N, x) * comb(N, y) % P

print(result % P)