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

import sys
input = sys.stdin.readline

N = int(input())
s = input().rstrip()
for t in ['SS', 'SW', 'WS', 'WW']:
    for i in range(1, N-1):
        if (t[-1] == 'W') ^ (s[i] == 'o') ^ (t[-2] == 'S'):
            t += 'W'
        else:
            t += 'S'
    if (t[-1] == 'W') ^ (s[-1] == 'o') ^ (t[-2] == t[0]):
        continue
    if (t[0] == 'W') ^ (s[0] == 'o') ^ (t[-1] == t[1]):
        continue
    print(t)
    exit()
print(-1)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
s = input().rstrip()
for t in ['SS', 'SW', 'WS', 'WW']:
    for i in range(1, N-1):
        if (t[-1] == 'W') ^ (s[i] == 'o') ^ (t[-2] == 'S'):
            t += 'W'
        else:
            t += 'S'
    if (t[-1] == 'W') ^ (s[-1] == 'o') ^ (t[-2] == t[0]):
        continue
    if (t[0] == 'W') ^ (s[0] == 'o') ^ (t[-1] == t[1]):
        continue
    print(t)
    exit()
print(-1)
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split())
a = [10**10] * n

edge = [[] for i in range(n)]

for i in range(m):
    l, r, d = map(int, input().split())
    l-=1;r-=1
    edge[l].append((r, d))
    edge[r].append((l, -d))

flag = True
for i in range(n):
    if not flag: break
    dist = [10**10]*n
    dist[i] = 0
    dq = deque([i])
    while dq:
        now = dq.popleft()
        for e in edge[now]:
            nnode, d = e
            if dist[nnode] == 10**10:
                dist[nnode] = dist[now] + d
                dq.append(nnode)
            else:
                if dist[nnode] != dist[now] + d:
                    flag = False
                    break
if flag:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
inf = pow(10, 10)

n, m = map(int, input().split())
a = [inf] * n

edge = [[] for i in range(n)]

for i in range(m):
    l, r, d = map(int, input().split())
    l-=1;r-=1
    edge[l].append((r, d))
    edge[r].append((l, -d))

flag = True
dist = [inf] * n
for i in range(n):
    if not flag: break
    if dist[i] == inf:
        dist[i] = 0
        dq = deque([i])
        while dq:
            now = dq.popleft()
            for e in edge[now]:
                nnode, d = e
                if dist[nnode] == inf:
                    dist[nnode] = dist[now] + d
                    dq.append(nnode)
                else:
                    if dist[nnode] != dist[now] + d:
                        flag = False
                        break
if flag:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

from collections import deque
# K = 3
# a = [1,3,5,4,2]
# N = len(a)

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

deq = deque()
min_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] >= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    min_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()
#print(min_val)

deq = deque()
max_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] <= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    max_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()
#print(max_val)

cnt = 0
preL = -1
prerange_min = -2
sortMatchCnt = 0
for i in range(N - K + 1):
  range_min = min_val[i]
  range_max = max_val[i]
  l = p[i]
  r = p[i + K - 1]

  sortMatchFlg = False
  if range_min == l and range_max == r:
    sortMatchFlg = p[i:i + K] == sorted(p[i:i + K])
    if sortMatchFlg:
      sortMatchCnt += 1                      

  if (preL == prerange_min and r == range_max) or sortMatchFlg:
    pass
  else:
    cnt += 1
  preL = l
  # preR = r
  prerange_min = range_min
  # prerange_max = range_max
if sortMatchCnt >= 1:
  print(cnt + 1)
else:
  print(cnt)


### FIXED CODE ###

from collections import deque
import itertools
# K = 3
# a = [1,3,5,4,2]
# N = len(a)

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

deq = deque()
min_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] >= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    min_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()
#print(min_val)

deq = deque()
max_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] <= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    max_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()
#print(max_val)

incr = [1 if x<y else 0 for x,y in zip(p, p[1:])]
incr_cum = [0] + list(itertools.accumulate(incr))
is_stable = [y-x==K-1 for x,y in zip(incr_cum,incr_cum[K-1:])]

cnt = 0
preL = -1
prerange_min = -2
sortMatchCnt = 0
for i in range(N - K + 1):
  range_min = min_val[i]
  range_max = max_val[i]
  l = p[i]
  r = p[i + K - 1]

  sortMatchFlg = False
  if is_stable[i]:
    sortMatchCnt += 1
    sortMatchFlg = True

  if (preL == prerange_min and r == range_max) or sortMatchFlg:
    pass
  else:
    cnt += 1
  preL = l
  # preR = r
  prerange_min = range_min
  # prerange_max = range_max
if sortMatchCnt >= 1:
  print(cnt + 1)
else:
  print(cnt)
### BUGGY CODE ###

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

BC_list = [list(map(int, input().split())) for _ in range(M)]
BC_list = [BC_list[i][1] for i in range(M) for _ in range(BC_list[i][0])]
A_list.extend(BC_list)
A_list.sort()

print(sum(A_list[-N:]))


### FIXED CODE ###

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

BC_list = [list(map(int, input().split())) for _ in range(M)]
BC_list = sorted(BC_list, key=lambda x: x[1])

ans = 0
count = 0
i = N-1
m = M-1
while count < N:
    if A_list[i] < BC_list[m][1]:
        for _ in range(BC_list[m][0]):
            ans += BC_list[m][1]
            count += 1
            if count >= N:
                break
        m -= 1
    else:
        ans += A_list[i]
        count += 1
        i -= 1

    if m < 0:
        break

for _ in range(count, N):
    ans += A_list[i]
    i -= 1

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

def solve(i,j,a):
    k=False
    sc=0
    pl=[]
    for v in [2,3,5,7,11,13,17,19]:
        if j%v==0:
            break
    v=j//v
    if a.count(j)>=2:
        k=True
    else:
        for c in a:
            if c>v:
                break
            elif c==j:
                sc+=1
                if sc>=2:
                    k=True
                    break
            else:
                if j%c==0:
                    k=True
                    break
    return k

n=int(input())
a=sorted(list(map(int,input().split())))
ans=0
for i,j in enumerate(a):
    if solve(i,j,a):
        continue
    else:
        ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
m=max(a)
cnt=[0 for _ in range(m+1)]
ans=0
for i in a:
    if cnt[i]>=1:
        cnt[i]+=1
        continue
    for j in range(2*i,m+1,i):
        cnt[j]+=1
    cnt[i]=1
for i in range(n):
    if cnt[a[i]]==1:
        ans+=1
print(ans)
### BUGGY CODE ###

N = int(input())
S = []
ans = N
for i in range(N):
    S.append(input())
    flg = 0
    j  = 0
    while(flg == 0 and j < i):
        if i != j:
            if len(S[j]) > 0:
                if S[j][0] == S[i][0]:
                    if S[j] == S[i]:
                        S[j] = ''
                        ans = ans - 1
                        flg = 1
        j = j+1
print(ans)

### FIXED CODE ###

N = int(input())
S = []
ans = N
S = [input() for i in range(N)]
#for i in range(N):
#    S.append(input())
S.sort()
for i in range(N-1):
    if S[i] == S[i+1]:
        ans = ans - 1
print(ans)
### BUGGY CODE ###

m=10**9+7
s=list(input())
n=len(s)
s.reverse()
dp=[[0]*13 for _ in range(n)]
if s[0]=="?":
    for i in range(10):
        dp[0][i]+=1
else:
    dp[0][int(s[0])]=1
x=1
for i in range(1,n):
    x=(x*10)%13
    for j in range(13):
        if s[i]=="?":
            if dp[i-1][j]!=0:
                for k in range(10):
                    dp[i][(j+k*x)%13]+=dp[i-1][j]
        else:
            if dp[i-1][j]!=0:
                dp[i][(j+int(s[i])*x)%13]+=dp[i-1][j]
print(dp[n-1][5]%m)

### FIXED CODE ###

m=10**9+7
s=list(input())
n=len(s)
s.reverse()
dp=[[0]*13 for _ in range(n)]
if s[0]=="?":
    for i in range(10):
        dp[0][i]+=1
else:
    dp[0][int(s[0])]=1
x=1
for i in range(1,n):
    x=(x*10)%13
    for j in range(13):
        if s[i]=="?":
            if dp[i-1][j]!=0:
                for k in range(10):
                    dp[i][(j+k*x)%13]+=dp[i-1][j]
                    dp[i][j]%=m
        else:
            if dp[i-1][j]!=0:
                dp[i][(j+int(s[i])*x)%13]+=dp[i-1][j]
                dp[i][j]%=m
print(dp[n-1][5]%m)
### BUGGY CODE ###

import numpy as np

H, W = [int(item) for item in input().split()]

grid = np.array([[item for item in input()] for _ in range(H)])
dp = np.zeros((H, W), dtype='int32')
max_num = 10**9 +7

def main():
    dp[0,0] = 1

    for i in range(H):
        for j in range(W):
            if grid[i, j] == '.' and i > 0 and j > 0:
                dp[i, j] = (dp[i-1, j] + dp[i, j-1]) % max_num
            elif grid[i, j] == '.' and i == 0 and j > 0:
                dp[i, j] = dp[i, j - 1] 
            elif grid[i, j] == '.' and j == 0 and i > 0:
                dp[i, j] = dp[i-1, j]

    # print(dp)
    print(dp[H-1,W-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

H, W = [int(item) for item in input().split()]
grid = [[item for item in input()] for _ in range(H)]

dp = [[0 for _ in range(W+1)] for _ in range(H+1)]
max_num = 10**9 +7

def main():
    dp[0][1] = 1

    for i in range(H):
        for j in range(W):
            if grid[i][j] != '#':
                dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j]) % max_num
            

    # print(dp)
    print(dp[H][W])

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

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

count = 0

count_dict = collections.defaultdict(int)

for idx, a in enumerate(A):
    if idx+a+1 in count_dict:
        count += count_dict[idx+a+1]
        continue
    for i in range(idx+a+1, N):
        if a + A[i] == i - idx:
            count += 1
            count_dict[idx+a+1] += 1

print(count)

### FIXED CODE ###

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

count = 0

count_dict = collections.defaultdict(int)

for idx, a in enumerate(A):
    count_dict[idx-a] += 1

for idx, a in enumerate(A):
    if idx+a in count_dict:
        count += count_dict[idx+a]
        continue
    # for i in range(idx+a+1, N):
    #     if a + A[i] == i - idx:
    #         count += 1
    #         count_dict[idx+a+1] += 1
# print(count_dict)

print(count)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

# 0以上整数x未満の素数のリストを返す(0,1は含まない)
import math
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0

    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

import bisect

def main():
    N = 10**5+1
    ps = primes(N)
    P = [0]*N
    for p in ps:
        P[p] = 1

    Q = int(input())
    for _ in range(Q):
        ans = 0
        l,r = map(int, input().split())
        li = bisect.bisect_left(ps, l)
        ri = bisect.bisect_right(ps, r)
        for i in range(li, ri):
            if P[(ps[i]+1)//2]:
                ans += 1
        print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline

# 0以上整数x未満の素数のリストを返す(0,1は含まない)
import math
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0

    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

def main():
    N = 10**5+1
    ps = primes(N)

    P = [0]*N
    for p in ps:
        P[p] = 1

    ruisekiwa = [0]*N
    for i in range(3, N, 2):
        if P[i] and P[(i+1)//2]:
            ruisekiwa[i] = 1
    for i in range(3, N):
        ruisekiwa[i] += ruisekiwa[i-1]
    
    Q = int(input())
    for _ in range(Q):
        l,r = map(int, input().split())
        ans = ruisekiwa[r] - ruisekiwa[l-1]
        print(ans)

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

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

l = [0] * N

for i in range(M):
    A, B = map(int, input().split())
    for j in range(A-1,B):
        l[j] += 1

ans = [k for k in l if k >= M]
print(len(ans))

### FIXED CODE ###

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

L_list = []
R_list = []

for i in range(M):
    A, B = map(int, input().split())
    L_list.append(A)
    R_list.append(B)

if max(L_list) > min(R_list):
    print(0)
else:
    print(min(R_list) - max(L_list) + 1)
### BUGGY CODE ###

#Mo
import sys
input = sys.stdin.readline
n,q=map(int, input().split())
*c,=map(int, input().split())
que=[]
for i in range(q):
    li,ri=map(int, input().split())
    que.append((li-1,ri-1,i))

que.sort(key
    =lambda x:(x[0]//1000,x[1]))

ll=0;rr=0
cnt=[0 for _ in range(500001)]
ans=[0 for _ in range(500001)]
col=0
cnt[c[0]]=1
for l,r,j in que:
    while rr<r:
        if cnt[c[rr+1]]==0:
            col+=1
        cnt[c[rr+1]]+=1
        rr+=1
    while rr>r:
        if cnt[c[rr]]==1:
            col-=1
        cnt[c[rr]]-=1
        rr-=1
    while ll>l:
        if cnt[c[ll-1]]==0:
            col+=1
        cnt[c[ll-1]]+=1
        ll-=1
    while ll<l:
        if cnt[c[ll]]==1:
            col-=1
        cnt[c[ll]]-=1
        ll+=1
    ans[j]=col+1
print('\n'.join(map(str,ans[:q])))


### FIXED CODE ###

import sys
input=sys.stdin.readline
n,q=map(int, input().split())
*c,=map(int, input().split())

qu=[list(map(int, input().split())) +[i] for i in range(q)]
qu.sort(key=lambda x:x[1])
bit=[0]*(n+1)

last=[-1]*(n+1)

def add(t,x):
    while t<=n:
        bit[t]+=x
        t += t&(-t)

def query(t):
    res=0
    while t:
        res+=bit[t]
        t-=t&(-t)
    return res

used=1
ans=[0]*q
for l,r,i in qu:
    while used<=r:
        add(used,1)
        if last[c[used-1]]>=0:
            add(last[c[used-1]],-1)
        last[c[used-1]]=used
        used+=1
    ansi=query(r)-query(l-1)
    ans[i]=ansi
for ansi in ans:
    print(ansi)
### BUGGY CODE ###

n,a = map(int,input().split())
x = list(map(int,input().split()))
x= sorted(x)
sho = sum(x)//a
dp = [[[[0]*(sho+1) for _ in range(a)]for _ in range(n+1)] for _ in range(n+1)]
#dp[i枚目まで選ぶ][選んだ枚数][aで割ったときの余り][aで割った商]=通り数

dp[0][0][0][0]=1 #何も選ばない

for i in range(0,n):
  j = x[i]%a
  kuwaeru = x[i]//a
  num = 0
  while num<=i:
    for k in range(a):
      for l in range(sho+1):
        if k+j<a and l+kuwaeru <= sho:
          dp[i+1][num+1][(k+j)%a][l+kuwaeru] += dp[i][num][k][l]  #i番目のカードを選ぶ
        elif k+j>=a and l+kuwaeru+1 <= sho:
          dp[i+1][num+1][(k+j)%a][l+kuwaeru+1] += dp[i][num][k][l]  #i番目のカードを選ぶ
  
        dp[i+1][num][k][l] += dp[i][num][k][l]  #i番目のカードを選ばない
    num +=1

ans = 0
for i in range(1,min(sho+1,n+1)):
  ans +=  dp[n][i][0][i]
print(ans)

### FIXED CODE ###

n,a = map(int,input().split())
x = list(map(int,input().split()))
x= sorted(x)
sho = sum(x)//a
dp = [[[[0]*(sho+1) for _ in range(a)]for _ in range(n+1)] for _ in range(n+1)]
#dp[i枚目まで選ぶ][選んだ枚数][aで割ったときの余り][aで割った商]=通り数

dp[0][0][0][0]=1 #何も選ばない

for i in range(0,n):
  j = x[i]%a
  kuwaeru = x[i]//a
  num = 0
  while num<=i:
    for k in range(a):
      for l in range(sho+1):
        if k+j<a and l+kuwaeru <= sho:
          dp[i+1][num+1][(k+j)%a][l+kuwaeru] += dp[i][num][k][l]  #i番目のカードを選ぶ
        elif k+j>=a and l+kuwaeru+1 <= sho:
          dp[i+1][num+1][(k+j)%a][l+kuwaeru+1] += dp[i][num][k][l]  #i番目のカードを選ぶ
  
        dp[i+1][num][k][l] += dp[i][num][k][l]  #i番目のカードを選ばない
    num +=1

ans = 0
for i in range(1,min(sho+1,n+1)):
  ans +=  dp[n][i][0][i]
print(ans)
### BUGGY CODE ###

import math
from collections import deque
a,b,c=[int(_) for _ in input().split()]
k=c-1
s=math.floor((k*a)/b)-a*math.floor(k/b)
t=math.floor((c*a)/b)-a*math.floor(c/b)
lista=set()
lista.add(s)
lista.add(t)
listb=deque()
t=0
while t<=c:
    t+=b-1
    if t>=c:
        if t==c:
           listb.append(t) 
        break
    listb.append(t) 
    t+=1
    listb.append(t)
for p in listb:
    lista.add(math.floor((p*a)/b)-a*math.floor(p/b))
print(max(lista))

### FIXED CODE ###

import math
from collections import deque
a,b,c=[int(_) for _ in input().split()]
if c>=b:
    k=b-1    
else:
    k=c
s=math.floor((k*a)/b)-a*math.floor(k/b)
print(s)
### BUGGY CODE ###

import sys
import statistics
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7



def main():
    N = int(readline())
    X = list(map(int, readline().split()))
    sort_X = sorted(X)
    for i in range(N):
        median = statistics.median(X[:i]+X[i+1:])
        print(median)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7



def main():
    N = int(readline())
    X = list(map(int, readline().split()))
    sort_X = sorted(X)
    if N%2==0:
        med_l = sort_X[N//2-1]
        med_r = sort_X[N//2]
        for i in range(N):
            if X[i]<=med_l:
                print(med_r)
            else:
                print(med_l)
    else:
        l = sort_X[N//2-1]
        m = sort_X[N//2]
        r = sort_X[N//2+1]
        for i in range(N):
            if X[i]<=l:
                print((m+r)/2)
            elif X[i]==m:
                print((l+r)/2)
            else:
                print((l+m)/2)


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

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

def comb(n, r) :
    if n - r < 0 or r < 0 :
        return 0
    
    r = min(n-r, r)

    a, b = 1, 1
    for i in range(r) :
        a *= n - i
        b *= i + 1

    return a // b

res = 0

for i in range(1, N + 1) :
    for j in range(1, M + 1) :
        if i > 1 and j > 1 :
            res += 2 * (N + 1 - i) * (M + 1 - j) * (i + j - 2)
        else :
            res += (N + 1 - i) * (M + 1 - j) * (i + j - 2)

res *= comb(N * M - 2, K - 2)

print(res % MOD)

### FIXED CODE ###

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

def pow(x, n) :
    y = 1
    while n > 0 :
        if n & 1 :
            y = (y * x) % MOD
        x = (x * x) % MOD
        n >>= 1

    return y

def comb(n, r) :
    if n < r or n < 0 :
        return 0

    factorial = [0] * (n + 1)
    factorial[0] = 1

    for i in range(1, n + 1) :
        factorial[i] = (factorial[i-1] * i) % MOD

    return (factorial[n] * pow(factorial[n-r], MOD - 2) * pow(factorial[r], MOD - 2)) % MOD

res = 0

for i in range(N) :
    for j in range(M) :
        if i > 0 and j > 0 :
            res += 2 * (N - i) * (M - j) * (i + j)
        else :
            res += (N - i) * (M - j) * (i + j)

res *= comb(N * M - 2, K - 2)

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

from collections import deque


def main():

    def f(hi, wi):
        return hi * w + wi

    h, w = map(int, input().split())
    sh, sw = map(int, input().split())
    gh, gw = map(int, input().split())

    s = [input() for _ in range(h)]
    INF = 10 ** 9

    sh -= 1
    sw -= 1
    gh -= 1
    gw -= 1

    dq = deque([f(sh, sw)])
    dist = [[INF] * w for _ in range(h)]
    dist[sh][sw] = 0

    while dq:
        i = dq.popleft()
        hi, wi = divmod(i, w)

        for dh in range(-2, 3):
            for dw in range(-2, 3):
                if dh == 0 and dw == 0:
                    continue
                nh = hi + dh
                nw = wi + dw
                if 0 <= nh <= h - 1 and 0 <= nw <= w - 1 and s[nh][nw] == ".":
                    if abs(dh) + abs(dw) == 1:
                        if dist[hi][wi] < dist[nh][nw]:
                            dist[nh][nw] = dist[hi][wi]
                            dq.appendleft(f(nh, nw))
                    else:
                        if dist[hi][wi] + 1 < dist[nh][nw]:
                            dist[nh][nw] = dist[hi][wi] + 1
                            dq.append(f(nh, nw))

    ans = dist[gh][gw]
    if ans == INF:
        ans = -1

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():

    def f(hi, wi):
        return hi * w + wi

    h, w = map(int, input().split())
    sh, sw = map(int, input().split())
    gh, gw = map(int, input().split())

    s = [input() for _ in range(h)]
    INF = 10 ** 9

    sh -= 1
    sw -= 1
    gh -= 1
    gw -= 1

    dq = deque([f(sh, sw)])
    dist = [[INF] * w for _ in range(h)]
    dist[sh][sw] = 0

    while dq:
        i = dq.popleft()
        hi, wi = divmod(i, w)

        for dh in range(-2, 3):
            for dw in range(-2, 3):
                if dh == 0 and dw == 0:
                    continue
                nh = hi + dh
                nw = wi + dw
                if 0 <= nh <= h - 1 and 0 <= nw <= w - 1 and s[nh][nw] == ".":
                    if abs(dh) + abs(dw) == 1:
                        if dist[hi][wi] < dist[nh][nw]:
                            dist[nh][nw] = dist[hi][wi]
                            dq.appendleft(f(nh, nw))
                    else:
                        if dist[hi][wi] + 1 < dist[nh][nw]:
                            dist[nh][nw] = dist[hi][wi] + 1
                            dq.append(f(nh, nw))

    ans = dist[gh][gw]
    if ans == INF:
        ans = -1

    print(ans)


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

# input
N, M = map(int, input().split())
a = []
a_append = a.append

for n in range(M):
    a_append(int(input()))

mod = 1000000007

# check
dp = {0: 1, 1: 1}
for n in range(2, N + 1):
    dp[n] = 0
    if n - 1 not in a:
        dp[n] += dp[n - 1]
    if n - 2 not in a:
        dp[n] += dp[n - 2]

print(dp[N] % mod)

### FIXED CODE ###

# input
N, M = map(int, input().split())
a = []
a_append = a.append

for n in range(M):
    a_append(int(input()))

mod = 1000000007

# check
check = [True] * (N + 1)
for i in a:
    check[i] = False

dp = {0: 1}
if check[1] is True:
    dp[1] = 1
else:
    dp[1] = 0

for n in range(2, N + 1):
    dp[n] = 0
    if check[n - 1] is True:
        dp[n] += dp[n - 1]
    if check[n - 2] is True:
        dp[n] += dp[n - 2]
    dp[n] %= mod

print(dp[N])
### BUGGY CODE ###

def sub():
    N, W = [int(e) for e in input().split()]
    ww = []
    vv = []
    for _ in range(N):
        w, v = [int(e) for e in input().split()]
        ww.append(w)
        vv.append(v)
    
    # dp_table = [[0]*(W+1)]*(N+1)
    dp_table = [[0 for _ in range(W+1)] for _ in range(N+1)]
    # print(len(dp_table), len(dp_table[0]))
    for i in range(N):
        for j in range(W):
            w_next = j+ww[i]
            v_next = vv[i]
            if w_next <= W:
                dp_table[i+1][w_next] = max(dp_table[i+1][w_next], dp_table[i][j] + v_next)
            dp_table[i+1][j] = max(dp_table[i+1][j], dp_table[i][j])


    print(max(dp_table[-1]))
    # print(max(dp_table))

sub()


### FIXED CODE ###

def sub():
    N, W = [int(e) for e in input().split()]
    ww = []
    vv = []
    for _ in range(N):
        w, v = [int(e) for e in input().split()]
        ww.append(w)
        vv.append(v)
    
    # dp_table = [[0]*(W+1)]*(N+1)
    dp_table = [[0 for _ in range(W+1)] for _ in range(N+1)]
    # print(len(dp_table), len(dp_table[0]))
    for i in range(N):
        for j in range(W):
            w_next = j+ww[i]
            v_next = vv[i]
            if w_next <= W:
                dp_table[i+1][w_next] = max(dp_table[i+1][w_next], dp_table[i][j] + v_next)
            dp_table[i+1][j] = max(dp_table[i+1][j], dp_table[i][j])


    print(max(dp_table[-1]))
    # print(max(dp_table))

sub()
### BUGGY CODE ###

r,g,b,n=map(int,input().split())

sum=0
for x in range(0,3001):
    for y in range(0,1+(3000-x*r)//g):
        if r*x+g*y<=n and (n-r*x-g*y)%b==0:
            sum+=1
print(sum)

### FIXED CODE ###

r,g,b,n=map(int,input().split())

sum=0
for x in range(0,1+(n//r)):
    for y in range(0,1+(n-x*r)//g):
        if (n-r*x-g*y)%b==0:
            sum+=1
print(sum)