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

NN, QQ = map(int, input().split())
SS = input('')
ll = [0]*(QQ)
rr = [0]*(QQ)
for ii in range(QQ):
    ll[ii], rr[ii] = map(int, input().split())
AC_indices = [0]*(NN)

for jj in range(NN-1):
    if SS[jj] == 'A' and SS[jj+1] == 'C':
        AC_indices[jj] += 1
        
for ii in range(QQ):
    print(sum(AC_indices[ll[ii]-1:rr[ii]-1]))

### FIXED CODE ###

NN, QQ = map(int, input().split())
SS = input('')
ll = [0]*(QQ)
rr = [0]*(QQ)
for ii in range(QQ):
    ll[ii], rr[ii] = map(int, input().split())

AC_indices = [0]*(NN)
for jj in range(NN-1):
    if SS[jj] == 'A' and SS[jj+1] == 'C':
        AC_indices[jj] += 1
        
cum_AC = [0]*(NN+1)
cum_AC[0] = AC_indices[0]
for jj in range(NN):
    cum_AC[jj+1] = cum_AC[jj] + AC_indices[jj]

for ii in range(QQ):
    print(cum_AC[rr[ii]-1]-cum_AC[ll[ii]-1])
### BUGGY CODE ###

N, M = [int(item) for item in input().split()]
A = [int(item) for item in input().split()]
B = []
C = []
A.sort()
A.append(0)
for i in range(M):
  b, c = [int(item) for item in input().split()]
  B.append(b)
  C.append(c)

B = [x for y, x in sorted(zip(C, B))][::-1]
C = sorted(C)[::-1]

res = 0
# print (A)
for i in range(M):
  b = B[i]
  c = C[i]
  cnt = 0
  while A[cnt] < c and cnt < len(A)-1:
    cnt += 1
  # print (A, b, c, cnt, res)
  if cnt > b:
    res += c*b+sum(A[cnt:])
    A = A[b:cnt] + [0]
  else:
    res += c*cnt+sum(A[cnt:])
    A = []
  if len(A) == 0:
    break
  
print (res + sum(A))

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1],reverse=True)
for b,c in bc:
    a.extend([c]*b)
    if len(a)>2*n:
        break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

n=int(input())
lst=list(map(int, input().split()))
order=[]
for i in range(1,n+1):
    order.append(str(lst.index(i)+1))
print(' '.join(order))

### FIXED CODE ###

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


order=[None]*N
for i in range(0,N):
    order[A[i]-1]=str(i+1)
print(' '.join(order))
### BUGGY CODE ###

N = input()
alist = list(map(int,input().split()))
s = 0
i = 0
for x in alist:
  num = 0
  i += 1
  j = 0
  for y in alist:
    j += 1
    if i != j:
      if x % y != 0:
        num += 1
  if num == int(N)-1:
    s += 1
print(s)
       

### FIXED CODE ###

'''
Created on 2020/08/23

@author: harurun
'''
def main():
  from collections import Counter
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  ans=0
  N=int(pin())
  A=list(map(int,pin().split()))
  c=Counter(A)
  t=max(A)
  dp=[True]*t
  for i in A:
    if dp[i-1]:
      n=2*i
      while n<=t:
        dp[n-1]=False
        n+=i
  for k in A:
    if c[k]==1 and dp[k-1]:
      ans+=1
  print(ans)
  return
main()
### BUGGY CODE ###

import math
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}



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

a, b = [0] * m, [0] * m
for i in range(m):
    a[i],b[i] = map(int,input().split())

uni = UnionFind(n)
def C(n):
    return n*(n-1)//2

f =[C(n)]
for i in range(m-1,-1,-1):
    com = C(n)
    na, nb = a[i]-1,b[i]-1

    uni.union(na, nb)
    members = uni.all_group_members()
    for v,w in members.items():
        if len(w)>1:
            com -= C(len(w))

    f.append(com)

f.reverse()
print(*f[1:])



### FIXED CODE ###

import math
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}



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

a, b = [0] * m, [0] * m

for i in range(m):
    a[i],b[i] = map(int,input().split())

uni = UnionFind(n)

def C(n):
    return n*(n-1)//2

f =[C(n)]
com = C(n)
for i in range(m-1,-1,-1):

    na, nb = a[i]-1,b[i]-1
    if not uni.same(na,nb):
        n1 = uni.size(na)
        n2 = uni.size(nb)
        uni.union(na,nb)

        com -= n1*n2
    # print(n1, n2)

    f.append(com)

f.reverse()
print(*f[1:])
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
mean = sum(A)//N
mini = min(A[0:L])
ans.append(mini - mean)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini-mean)
for i in ans[:-1] : print(i+mean, end=" ")
print(ans[-1]+mean)

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
S=input()
N=int(len(S))
for _ in list(S):
    A=S
    S=S.replace("10","")
    S=S.replace("01","")
    if A==S:
        break
print(N-int(len(S)))

### FIXED CODE ###

S=input()
print(min(S.count("0"),S.count("1"))*2)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
mod = 10**9 + 7

for i in range(n-1):
    for j in range(i+1, n):
        #print(a[i] ^ a[j])
        ans += (a[i] ^ a[j]) % mod

print(ans % mod)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 0

for i in range(60):
    zeroCnt = 0
    oneCnt = 0

    for j in range(n):
        if (a[j] >> i) & 1 == 1:
            oneCnt += 1
        else:
            zeroCnt += 1
    ans += zeroCnt * oneCnt * pow(2, i, mod)
    ans %= mod

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

def solve(s):
    s = list(s)
    n = len(s)
    res = 0
    i = 0
    before = list("ABC")
    after = list("BCA")
    m = len(before)
    while i+m <= n:
        if s[i:i+m] == before:
            s[i:i+m] = after
            i = max(0, i-1)
            res += 1
        else:
            i += 1
    return res

s = input()
print(solve(s))

### FIXED CODE ###

def solve(s):
    n = len(s)
    res = 0
    i = 0
    num = 0
    while i < n-1:
        if s[i] == "A":
            num += 1
            i += 1
        elif s[i:i+2] == "BC":
            res += num
            i += 2
        else:
            num = 0
            i += 1
    return res

s = input()
print(solve(s))
### BUGGY CODE ###

N = int(input())
values = list(map(int, input().split()))
keys = list(range(1, N + 1))
A = dict(zip(keys, values))

count = 0
for i in range(N):
    for j in range(i + 1, N):
        if abs(i - j) == values[i] + values[j]:
            count += 1

print(count)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
values = list(map(int, input().split()))
keys = list(range(1, N + 1))

memo = defaultdict(int)
count = 0
for i, x in enumerate(values):
    count += memo[i - x]
    memo[i + x] += 1
print(count)
### BUGGY CODE ###

K=int(input())
ANS=[]
for i in range(1,10**6*5):
  LEN=len(str(i))
  STR=str(i)
  if LEN==1:
    ANS+=[i]
  for k in range(LEN-1):
    if abs(int(STR[k])-int(STR[k+1]))>1:
      break
    if k==LEN-2:
      ANS+=[i]
ans=ANS[K-1] 
print(ans)

### FIXED CODE ###

K=int(input())
ANS=[i for i in range(1,10)]
i=0
while len(ANS)<=10**5:
  last=str(ANS[i])[-1]
  if last=="0":
    ANS+=[ANS[i]*10,ANS[i]*10+1]
  elif last=="9":
    ANS+=[ANS[i]*10+8,ANS[i]*10+9]
  else:
    ANS+=[ANS[i]*10+int(last)-1,ANS[i]*10+int(last),ANS[i]*10+int(last)+1]
  i+=1  
ans=ANS[K-1]
print(ans)
### BUGGY CODE ###

# coding: utf-8
n = int(raw_input())
li = map(int, raw_input().split())

count = 0

for i in xrange(n):
    for j in xrange(i+1,n):
        for k in xrange(j+1,n):
            if li[i] < li[j] + li[k] and li[j] < li[i] + li[k] and li[k] < li[i] + li[j]:
                count +=1
print count


### FIXED CODE ###

# coding: utf-8
n = int(raw_input())
L = map(int, raw_input().split())

#昇順にソート
L.sort()

ans = 0



for a in xrange(n-2):
	c = a + 2
	for b in xrange(a+1,n-1):
		while c < n and L[a] + L[b] > L[c]:
			c += 1
		if c > b:
			ans += (c-b-1)
print ans
### BUGGY CODE ###

n, *ps = map(int, open(0).read().split())
cou = 1
for i, p in enumerate(ps[1:], 2):
  a = sorted(ps[:i])
  if a.index(p)==0:
    cou += 1
print(cou)

### FIXED CODE ###

n, *ps = map(int, open(0).read().split())
mp = ps[0]
cou = 1
for p in ps[1:]:
  if mp > p:
    cou += 1
    mp = p
print(cou)
### BUGGY CODE ###

n = int(input())
flag = False
limit = 1000000000000000000
a = [int(item) for item in input().split()]
ans = 1
for i in a:
    ans = ans*i
if(ans > limit):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
flag = False
limit = 1000000000000000000
a = [int(item) for item in input().split()]
ans = 1
for i in a:
    if(i == 0):
        flag = True
        break
for i in a:
    ans = ans*i
    if(ans > limit):
        break
if(flag):
    print(0)
elif(ans > limit):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

# グラフわからんのでグラフアルゴリズム忘れた
# dfsでやる 限度2回

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)


def dfs(t, c):
    if c != 0 and t == n - 1:
        return True
    if c == 0:
        return False
    flag = False
    for g in graph[t]:
        flag = dfs(g, c - 1)
        if flag:
            break
    return flag


for x in graph[0]:
    if dfs(x, 2):
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")


### FIXED CODE ###

# グラフわからんのでグラフアルゴリズム忘れた
# dfsでやる 限度2回c
# なんかしらんけどdfsが2TLEになるので諦めた それぞれの島について1とNがあれば良い

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

for g in graph[1 : n - 1]:
    c = 0
    for v in g:
        if c >= 2:
            break
        if v == 0 or v == n - 1:
            c += 1
    if c == 2:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

s = input()
l = len(s)
ans = 0
for i in range(0, l-4):
    for j in range(i+3, l):
        num = int(s[i:j+1])
        if num%2019 == 0:
            ans += 1
print(ans)

### FIXED CODE ###

s = input()
s = s[::-1]
l = len(s)
count = [0] * 2019
res = 0
count[res] = 1
d = 1
for i in s:
    res += int(i) * d
    res %= 2019
    count[res] += 1
    d *= 10
    d %= 2019
print(int(sum([m*(m-1)/2 for m in count])))
### BUGGY CODE ###

import heapq
l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
dh=DH-1
dw=DW-1
S=[[x=='#' for x in list(input())] for _ in range(H)]
q=[(0,0,CH-1,CW-1)]
heapq.heapify(q)
checked=set()
def check(h,w,c):
    if h<0 or h>=H or w<0 or w>=W:
        return
    if S[h][w]:
        return
    p=(abs(dh-h),abs(dw-w))
    heapq.heappush(q,(c,p,h,w))

def main():
    while q:
        c,_,h,w=heapq.heappop(q)
        if h==dh and w==dw:
            return c
        key=(h,w)
        if key in checked:
            continue
        checked.add(key)
        # walk
        check(h-1,w-0,c)
        check(h-0,w-1,c)
        check(h+1,w+0,c)
        check(h+0,w+1,c)
        # warp
        check(h-1,w-1,c+1)
        check(h-1,w+1,c+1)
        check(h+1,w-1,c+1)
        check(h+1,w+1,c+1)
        for i in [-2,+2]:
            for j in range(-2,3):
                check(h+i,w+j,c+1)
                check(h+j,w+i,c+1)
    return -1
print(main())


### FIXED CODE ###

def l():
    return [int(x) for x in input().split()]
def main():
    H,W=l()
    ch,cw=l()
    dh,dw=l()
    ch-=1
    cw-=1
    dw-=1
    dh-=1
    s=[[-2 if x=='#' else -1 for x in list(input())] for _ in range(H)]
    pad1=[-2,-2]
    pad2=[[-2]*(W+4)]*2
    s=pad2+[pad1+x+pad1 for x in s]+pad2
    move1=[(-1,0),(1,0),(0,-1),(0,1)]
    move2=list(set([(i,j) for i in range(-2,3) for j in range(-2,3)])-set(move1)-set([(0,0)]))
    q1=[(0,ch+2,cw+2)]
    q2=[]
    s[ch+2][cw+2]=0
    def mark(c,h,w):
        #if 0<=h<H and 0<=w<W and s[h][w]==-1:
        if s[h][w]==-1:
            s[h][w]=c
            q1.append((c,h,w))
    while q1:
        #print(q1)
        c,h,w=q1.pop()
        for i,j in move1:
            mark(c,h+i,w+j)
        q2.append((c+1,h,w))
        if not q1:
            for c,h,w in q2:
                for i,j in move2:
                    mark(c,h+i,w+j)
            q2=[]
    ans=s[dh+2][dw+2]
    if ans>=0:
        print(ans)
    else:
        print(-1)
main()
### BUGGY CODE ###

(n,q),*t=[map(int,t.split())for t in open(0)]
s=[0]
d=s*n
f=s+[1]*n
e=[[]for _ in d]
for a,b in t[:-q]:e[a-1]+=b-1,;e[b-1]+=a-1,
for p,x in t[-q:]:d[p-1]+=x
while s:
 v=s.pop()
 for w in e[v]:d[w]+=d[v]*f[w];s+=[w]*f[w];f[w]=0
print(*d)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def dfs(v):
    for w in e[v]:
        if root[w]>=0:continue
        root[w]=v
        dfs(w)
def dfs2(v):
    for w in e[v]:
        if f[w]:continue
        f[w]=1
        data[w]+=data[v]
        dfs2(w)
input=sys.stdin.readline
n,q=map(int,input().split())
e=[[]for _ in range(n)]
root=[0]+[-1]*(n-1)
data=[0]*n
for _ in range(n-1):
    a,b=map(int,input().split())
    e[a-1]+=b-1,
    e[b-1]+=a-1,
#dfs(0)
for _ in range(q):
    p,x=map(int,input().split())
    data[p-1]+=x
f=[1]+[0]*(n-1)
dfs2(0)
print(*data)
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    A = [int(x) - 1 for x in input().split()]

    way = []
    now = 0
    for _ in range(K):
        if now in way:
            loop_start = way.index(now)
            K -= len(way[:loop_start])
            K %= len(way[loop_start:])
            for k in range(K):
                now = A[now]
            break
        way.append(now)
        now = A[now]
    print(now + 1)



if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    A = [int(x) - 1 for x in input().split()]

    way = []
    seen = [False for _ in [0] * (2 * 10 ** 5 + 1)]
    now = 0
    for _ in range(K):
        if seen[now]:
            loop_start = way.index(now)
            loop = way[loop_start:]
            K -= len(way[:loop_start])
            now = loop[K % len(loop)]
            break
        way.append(now)
        seen[now] = True
        now = A[now]
    print(now + 1)


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

H,N=map(int,input().split())
AB=[]
for i in range(N):
    AB.append(list(map(int,input().split())))
maxh=10**4
#dp[i] ひとつ前までの呪文で体力iを削るために必要な最小魔法消費量
dp=[float("inf")]*(2*maxh+1)
ndp=[float("inf")]*(2*maxh+1)
dp[0]=0
for j in range(N):
    for i in range(H+1):
        ndp[i]=dp[i]
    cost=AB[j][1]
    fire=AB[j][0]
    for i in range(H+1):
        repeat=0
        while i+fire*repeat<H:
            repeat+=1
            ndp[i+fire*repeat]=min(dp[i]+cost*repeat,ndp[i+fire*repeat])
    dp=ndp[:]

ans=float("inf")
for i in range(H,2*maxh+1):
    ans=min(ans,dp[i])
print(ans)







### FIXED CODE ###

H,N=map(int,input().split())
AB=[]
for i in range(N):
    AB.append(list(map(int,input().split())))
maxA=max(AB)[0]
#dp[i] 敵に合計iダメージを与えるのに必要な最小魔力量
dp=[float("inf")]*(H+maxA)
dp[0]=0
for i in range(H):
    for fire,cost in AB:
        dp[i+fire]=min(dp[i+fire],dp[i]+cost)

ans=min(dp[H:])
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


### FIXED CODE ###

# DP
def main():
    N, W = map(int, input().split())

    dp = [-1] * (W + 1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] == -1:
                continue
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v
    print(max(dp))


main()
### BUGGY CODE ###

N,P = list(map(int,input().split()))
S = input()

if P == 2:
    c = 0
    for i in range(N):
        u = int(S[i])
        if u % 2 == 0:
            c += i+1
    print(c)
        
elif P == 5:
    c = 0
    for i in range(N):
        u = int(S[i])
        if u % 5 == 0:
            c += i+1
    print(c)

else:
    U = [0]
    a = 0
    t = 1
    
    for i in range(N):
        t %= P
        a += int(S[-i-1])*t
        a %= P
        t *= 10
        U.append(a)
    # print(U)
    
    c = 0
    for i in range(P):
    
        m = U.count(i)
        c += m*(m-1)//2
    print(c)

### FIXED CODE ###

# import time

N,P = list(map(int,input().split()))
S = input()

if P == 2:
    c = 0
    for i in range(N):
        u = int(S[i])
        if u % 2 == 0:
            c += i+1
    print(c)
        
elif P == 5:
    c = 0
    for i in range(N):
        u = int(S[i])
        if u % 5 == 0:
            c += i+1
    print(c)

else:
    U = [0]
    a = 0
    t = 1
    
    for i in range(N):
        t %= P
        a += int(S[-i-1])*t
        a %= P
        t *= 10
        U.append(a)
    U.append(10001)
    # print(U)
    
    # t3 = time.time()
    
    c = 0
    
    """
    for i in range(P):
        m = U.count(i)
        c += m*(m-1)//2
    print(c)
    """
    U.sort()
    # print(U)
    idx = 0
    q = -1
    for i in range(N+2):
        if q != U[i]:
            q = U[i]
            m = i - idx
            idx = i
            c += m*(m-1)//2
    print(c)
    # t4 = time.time()
    # print(t4-t3)
    
    # 10032
### BUGGY CODE ###

n, k = map(int, input().split())
h_list = list(map(int, input().split()))
costs = [0] * n
costs[1] = abs(h_list[0] - h_list[1])
start = 0
for i in range(2, n):
    tmp = []
    v = h_list[i]
    if i-k >= 0:
        start = i-k
    else:
        start = 0
    for l in range(start, i):
        if abs(v - h_list[l]) == 0:
            tmp = [abs(v - h_list[l])+costs[l]]
            break
        tmp.append(abs(v - h_list[l])+costs[l])
    costs[i] = min(tmp)
print(costs[-1])


### FIXED CODE ###

n, k = map(int, input().split())
h_list = list(map(int, input().split()))
costs = [0] * n
costs[1] = abs(h_list[0] - h_list[1])
start = 0
for i in range(2, n):
    tmp = []
    v = h_list[i]
    start = max(0, i-k)
    costs[i] = min(abs(v - h_j) + c for h_j, c in zip(h_list[start:i], costs[start:i]))
    # for l in range(start, i):
    #     tmp.append(abs(v - h_list[l])+costs[l])
    #     if abs(v - h_list[l]) == 0:
    #         break
    # costs[i] = min(tmp)
print(costs[-1])
### BUGGY CODE ###



def main():
    n = int(input())
    pp = []
    for _ in range(n):
        pp.append(int(input()))

    xx = [None] * n
    for s in range(n - 1, -1, -1):
        if xx[s] is not None:
            continue
        count = 1
        pre = pp[s]
        for i in range(s+1, n):
            if pre + 1 == pp[i]:
                if xx[i] is not None:
                    xx[s] = xx[i] + count
                    break
                pre = pp[i]
                count += 1
        else:
            xx[s] = count
    print(n - max(xx))


if __name__ == '__main__':
    main()


### FIXED CODE ###



def main():
    n = int(input())
    pp = []
    for _ in range(n):
        pp.append(int(input()))
    dd = {}
    for i in range(n):
        dd[pp[i]] = i

    xx = [-1] * n
    for s in range(n - 1, -1, -1):
        if xx[s] >= 0:
            continue
        count = 1
        pre = pp[s]
        while pre + 1 in dd and dd[pre + 1] > s:
            i = dd[pre + 1]
            if xx[i] >= 0:
                xx[s] = xx[i] + count
                break
            pre += 1
            count += 1
        else:
            xx[s] = count
    print(n - max(xx))


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

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

ans = 0
for i in range(n//r+1):
    """
    if n % r == 0:
        ans += 1
        continue
    """
    if n - r*i < 0:
        continue
    for j in range(n//g+1):
        """
        if n % g == 0:
            ans += 1
            continue
        """
        if n - r*i - g*j < 0:
            continue
        if (n - r*i - g*j)%b == 0:
            ans += 1

        # print(n,i,j,n - i*r - j*g,ans)
print(ans)


### FIXED CODE ###

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

ans = 0
for i in range(n//r+1):
    for j in range((n-r*i)//g+1):
        if (n - r*i - g*j)%b == 0:
            ans += 1
print(ans)