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

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

if N == 1:
	if a[0] >= K:
		print(0)
	else:
		print(1)

else:
	def check(i):
		if a[i] >= K:
			return True
		if i == 0:
			b = a[1:]
		elif i == N - 1:
			b = a[:N - 1]
		else:
			b = a[:i] + a[i+1:]
		#print(b)
		#ok = False
		#dp = [[False] * K for _ in range(N - 1)]
		dp = [False] * K
		#dp[0] = True
		if b[0] < K:
			#dp[0][b[0]] = True
			dp[b[0]] = True
		if K - a[i] <= b[0] < K:
			return True
		for j in range(1, N - 1):

			dp2 = [False] * K
			#if b[j] < K:
				#dp[b[j]] = True
			for k in range(1, K):
				#if b[j] == K:
				#	return True
				#elif dp[j - 1][k] == True:
				if dp[k] == True:
					dp2[k] = True
					if K - a[i] <= k:
						return True
				
				#elif k > b[j]:
				
				if k >= b[j]:
					#if dp[j - 1][k - b[j]] == True:
					if dp[k - b[j]] == True:
						#dp[j][k] = True
						dp2[k] = True
						if K - a[i] <= k:
							return True

			#print(dp)
			dp = dp2

		return False


	def bi_search(lower, upper):
		#print(lower, upper)
		mid = (lower + upper) // 2
		#print(mid)
		if mid == 0 and check(mid) == True:
			return 0
		elif mid == N - 2 and check(mid + 1) == False:
			return N
		elif check(mid) == False and check(mid + 1) == True:
			#print("hoge")
			return mid + 1
		elif check(mid) == True:
			return bi_search(lower, mid)
		else:
			return bi_search(mid, upper)


	print(bi_search(0, N - 1))


### FIXED CODE ###

import sys

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    if sum(dp[k-x:k]):
        return True
    else:
        return False

if check(1):
    print(0)
    sys.exit()

if not check(n):
    print(n)
    sys.exit()

while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if check(mi):
        ba = mi
    else:
        fr = mi

print(fr)
### BUGGY CODE ###

import sys
def input():
  return sys.stdin.readline().rstrip()
n, k = [int(i) for i in input().split()]
h = sorted(int(input()) for _ in range(n))
a = float("inf")
for i in range(n - k + 1):
  hik = h[i:i + k]
  a = min(a, hik[-1] - hik[0])
print(a)

### FIXED CODE ###

import sys
def input():
  return sys.stdin.readline().rstrip()
n, k = [int(i) for i in input().split()]
h = sorted(int(input()) for _ in range(n))
print(min(h[i + k - 1] - h[i] for i in range(n - k + 1)))
### BUGGY CODE ###


def main():
    import sys
    input = sys.stdin.buffer.readline
    #n = int(input())
    #l = list(map(int, input().split()))
    '''
    A=[]
    B=[]
    for i in range():
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)'''

    n,m = map(int, input().split())
    r=[[0 for i in range(n)]for i in range(n)]
    start = [0, 0]
    #print(bfs(h, w, m, start))
    for i in range(m):
        a,b=map(int, input().split())
        r[a-1][b-1]=b-1
        r[b-1][a-1]=a-1
    #print(r)

    def bfs(n,r,start):
        #始点に対して終点"g"に着けるか判定
        from collections import deque
        d = [0 for i in range(n)]
        visited=[False for i in range(n)]
        flg = True
        queue=deque([0])
        dd=0
        while queue:
            now=queue.popleft()
            visited[now]=True
            #print(now)
            for i in r[now]:
                if not visited[i]:
                    queue.append(i)
                    visited[i]=True
                    d[i]=now
        #print(d)
        if flg:
            print("Yes")
            for i in range(1,n):
                print(d[i]+1)
        else:
            print("No")
        return
    bfs(n,r,start)

if __name__ == "__main__":
     main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    #n = int(input())
    #l = list(map(int, input().split()))
    '''
    A=[]
    B=[]
    for i in range():
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)'''

    n,m = map(int, input().split())
    r=[[]for i in range(n)]
    start = [0, 0]
    #print(bfs(h, w, m, start))
    for i in range(m):
        a,b=map(int, input().split())
        r[a-1].append(b-1)
        r[b-1].append(a-1)
    #print(r)
    
    from collections import deque
    d = [0 for i in range(n)]
    visited=[False for i in range(n)]
    flg = True
    queue=deque([0])
    dd=0
    while queue:
        now=queue.popleft()
        visited[now]=True
        #print(now)
        for i in r[now]:
            if visited[i]:
                continue
            queue.append(i)
            visited[i]=True
            d[i]=now

    print("Yes")
    for i in range(1,n):
        print(d[i]+1)


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

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

ans = 0
for i in range(1, K+1):
    for h in range(1, K+1):
        for j in range(1, K+1):
            ans += gcd(i, h, j)

print(ans)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

ans = 0
for i in range(1, K+1):
    for h in range(1, K+1):
        for j in range(1, K+1):
            ans += gcd(i, h, j)

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

def power_func(a, b, p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

def comb(n, k, p, exp_table):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a = exp_table[n]
  b = power_func(exp_table[k], p-2, p)
  c = power_func(exp_table[n-k], p-2, p)
  return (a*b*c)%p
  
n, a, b = map(int, input().split())

MOD = 10**9 + 7
exp_table = [1]
for i in range(1, n+1):
    exp_table.append(exp_table[-1]*i%MOD)


print(2**n - 1 - comb(n, a, MOD, exp_table) - comb(n, b, MOD, exp_table))

### FIXED CODE ###

from functools import reduce
  
def comb(n, k, p):
  """power_funcを用いて(nCk) mod p を求める"""
  a = reduce(lambda x,y: x*y%p, range(n,n-k,-1))
  b = reduce(lambda x,y: x*y%p, range(1,k+1))
  return (a*pow(b, p-2, p))%p
  
n, a, b = map(int, input().split())

MOD = 10**9 + 7


print((pow(2,n,MOD) - 1 - comb(n, a, MOD) - comb(n, b, MOD))%MOD)
### BUGGY CODE ###

N, W = map(int, input().split())
I = [list(map(int, input().split())) for i in range(N)]
dp = [0] * (W+1)

for i in range(N):
  wi, vi = I[i]
  for w in range(W, wi-1, -1):
    dp[w] = max(dp[w], dp[w-wi]+vi)

print(dp[W])


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
def main():
    N,W = map(int,input().split())
    dp = [-1 for _ in range(W+1)]
    dp[W] = 0
    for _ in range(N):
        nm,nv = [int(a) for a in input().split()]
        for j in range(nm,W+1):
            a = nm
            if dp[j] == -1:
                continue
            if dp[j-a] < dp[j] + nv:
                dp[j-a] = dp[j] + nv
    print(max(dp))
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = int(input())
v = [int(i) for i in input().split()]

l = []
cnt = [0] * N

for ind, i in enumerate(v):
	if not i in l:
		l.append(i)
	cnt[ind] = l.index(i)

ret = 0
for i, c in enumerate(cnt):
	if i % 2 == 0:
		if c != 0:
			ret += 1
	else:
		if c != 1:
			ret += 1

print(ret)


### FIXED CODE ###

from collections import Counter
N = int(input())
v = list(map(int, input().split()))
e = []
o = []
for idx, i in enumerate(v):
    if idx % 2 == 0:
        o.append(i)
    else:
        e.append(i)

e = Counter(e).most_common()
o = Counter(o).most_common()
e1 = e[0][1]
e2 = e[1][1] if len(e) > 1 else 0
o1 = o[0][1]
o2 = o[1][1] if len(o) > 1 else 0
cnt = 0
if e[0][0] != o[0][0]:
    cnt = N - e1 - o1
else:
    o = N - e1 - o2
    e = N - e2 - o1
    cnt = min(o, e)
print(cnt)
### BUGGY CODE ###

# coding: utf-8

n = int(input())
words = []
ans = 0

for i in range(n):
  sort = sorted(input())
  t = ''.join(sort)
  if t in words:
    ans += words.count(t)
    
  words.append(t)
  
print(ans)

### FIXED CODE ###

# coding: utf-8

n = int(input())
words = {}
ans = 0

for i in range(n):
  t = ''.join(sorted(input()))
  if t in words:
    ans += words[t]
    words[t] += 1
  else:
    words[t] = 1
    
print(ans)
### BUGGY CODE ###

Matches = {str(num): c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}


def solve(N, M, As):
    Ms = {num: c for num, c in Matches.items() if int(num) in As}
    dp = ["-1" for _ in range(N + 1)]
    dp[0] = "0"
    for n in range(N + 1):
        for num, c in Ms.items():
            if n - c >= 0:
                if dp[n - c] == "-1":
                    continue
                if dp[n - c] == "0":
                    dp[n] = str(max(int(num), int(dp[n])))
                else:
                    dp[n] = str(max(int(dp[n - c] + num),
                                int(num + dp[n - c]),
                                int(dp[n])))
    return int(dp[N])

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, M, As))


### FIXED CODE ###

Matches = {num: c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}


def solve(N, M, As):
    dp = [-1 for _ in range(N + 1)]
    dp[0] = 0
    for a in sorted(As, reverse=True):
        c = Matches[a]
        for i in range(N - c + 1):
            if dp[i] == -1:
                continue
            dp[i + c] = max(dp[i+c],
                            dp[i] * 10 + a)
    return dp[N]

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, M, As))
### BUGGY CODE ###

a, b, k = map(int, input().split())
for i in range(a,b+1):
    if a+k > i >= a or b-k < i <= b:
        print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
if b-a+2 >2*k:
    for i in range(a,a+k):
        print(i)
    for i in range(b-k+1,b+1):
        print(i)
else:
    for i in range(a,b+1):
        print(i)
### BUGGY CODE ###

import sys
import numpy as np

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

x=np.zeros((N+1,N+1),dtype=np.int32)
for _ in range(M):
    l,r=map(int,input().split())
    x[l][r]+=1

x=np.cumsum(x,axis=0)
x=np.cumsum(x,axis=1)
for _ in range(Q):
    p,q=map(int,input().split())
    print(x[N][q]-x[p-1][q])

### FIXED CODE ###

import sys
import numpy as np

input=sys.stdin.readline

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

x=np.zeros((N+1,N+1),dtype=np.int32)
for _ in range(M):
    l,r=map(int,input().split())
    x[l,r]+=1

x=np.cumsum(x,axis=0)
x=np.cumsum(x,axis=1)
for _ in range(Q):
    p,q=map(int,input().split())
    print(x[N,q]-x[p-1,q])
### BUGGY CODE ###

import sys
input = sys.stdin.readline


class SegmentTree():
    def __init__(self, S):
        self.size = 19
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    def subquery(self, l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        # [l,r)に含まれる文字の種類数
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    tree = SegmentTree(S)
    for q in range(Q):
        t, i, c = input().split()
        if t == '1':
            i = int(i) - 1
            tree.update(i, c)
        else:
            l, r = int(i) - 1, int(c)
            print(tree.query(l, r))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


class SegmentTree():
    def __init__(self, S):
        self.size = 19
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    def subquery(self, l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        # [l,r)に含まれる文字の種類数
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


def main():
    N = int(input())
    S = [ord(_) - 97 for _ in list(input())]
    Q = int(input())
    tree = SegmentTree(S)
    for q in range(Q):
        t, i, c = input().split()
        if t == '1':
            i = int(i) - 1
            tree.update(i, ord(c) - 97)
        else:
            l, r = int(i) - 1, int(c)
            print(tree.query(l, r))


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

a,b,n=map(int,input().split())
'''
lst=[]
for i in range(n+1):
    now=int(a*i/b)-a*int(i/b)
    lst.append(now)
print(max(lst))
'''
now=0
if n>=b:
    if n//b>=500000:
        ans=int(a*(n-1)/b)-a*int((n-1)/b)
        ans2=int(a*n/b)-a*int(n/b)
        for i in range(0,n//b+1,20000):
            ans3=int(a*(i*b-1)/b)-a*int((i*b-1)/b)
            now=max(now,ans3)
        print(max(ans,ans2,now))
        exit()
    ans=int(a*(n-1)/b)-a*int((n-1)/b)
    ans2=int(a*n/b)-a*int(n/b)
    for i in range(n//b+1):
        ans3=int(a*(i*b-1)/b)-a*int((i*b-1)/b)
        now=max(now,ans3)
    print(max(ans,ans2,now))

else:
    ans=int(a*(n)/b)-a*int((n)/b)
    print(max(ans,0))

### FIXED CODE ###

a,b,n=map(int,input().split())
def ans(x):
    return int(a*x/b)
print(ans(min(n,b-1)))
### BUGGY CODE ###

n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
total=[0]*(n+1)
for i in xrange(n):
    if a[i]>0:
        total[i+1]=total[i]+a[i]
    else:
        total[i+1]=total[i]
ans=0
for i in xrange(n-k+1):
    tmp=0
    for j in xrange(i,i+k):
        tmp+=a[j]
    ans=max(ans,tmp+total[i]+total[n]-total[i+k],total[i]+total[n]-total[i+k])

print(ans)


### FIXED CODE ###

n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
total=[0]*(n+1)
asum=[0]*(n+1)
for i in xrange(n):
    asum[i+1]=asum[i]+a[i]
    if a[i]>0:
        total[i+1]=total[i]+a[i]
    else:
        total[i+1]=total[i]
ans=0
for i in xrange(n-k+1):
    tmp=asum[i+k]-asum[i]
    ans=max(ans,tmp+total[i]+total[n]-total[i+k],total[i]+total[n]-total[i+k])

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

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

L=[[0]*2 for i in range(M)]

for i in range(M):
    L[i][0] , L[i][1] = map(int, input().split())

A=[10**10]*M
B=[10**9]*M

L=sorted(L ,key=lambda x: x[0])

for i in range(M):
    if L[i][0] == 1:
        A[i]=L[i][1]
    else:
        break

L=sorted(L ,key=lambda x: -x[1])

for i in range(M):
    if L[i][1] == N:
        B[i]=L[i][0]
    else:
        break

for i in B:
    if i == 10**10 : 
        print("IMPOSSIBLE")
        exit()
    if i in A:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")


### FIXED CODE ###

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

L=[[0]*2 for i in range(M)]

for i in range(M):
    L[i][0] , L[i][1] = map(int, input().split())

A=[0]*M
B=[0]*M

L=sorted(L ,key=lambda x: x[0])

for i in range(M):
    if L[i][0] == 1:
        A[i]=L[i][1]
    else:
        break
A=A[0:i]

L=sorted(L ,key=lambda x: -x[1])

for i in range(M):
    if L[i][1] == N:
        B[i]=L[i][0]
    else:
        break
B=B[0:i]

if((len(A)==0)or(len(B)==0)):
    print("IMPOSSIBLE")
    exit()
if((max(A)<min(B))or(max(B)<min(A))):
    print("IMPOSSIBLE")
    exit()

A.sort()
B.sort()
i=0
j=0
while((i<len(A))and(j<len(B))):
    if A[i] == B[j]:
        print("POSSIBLE")
        exit()
    elif A[i] > B[j]:j+=1
    else:i+=1
print("IMPOSSIBLE")
### BUGGY CODE ###

import math as m

def judge_prime(num):
    isPrime = [True]*(num+1)
    isPrime[0] = False
    isPrime[1] = False
    border = m.sqrt(num)
    i = 2
    while i <= border:
        if isPrime[i]:
            j = i*2
            while j <= num:
                isPrime[j] = False
                j += i
        i += 1
        
    prime_list = []
    for prime in range(num+1):
        if isPrime[prime]:
            prime_list.append(prime)
        
    return prime_list
        
    
    
def main():
    #input
    Q1 = 1
    LR1 = [[3,7]]
    
    Q2 = 4
    LR2 = [[13, 13],
                [7, 11],
                [7, 11],
                [2017, 2017]]
    
    
    Q = Q2
    LR = LR2

    # 1. find 2017-like number
    MAX_Q = 10**5
    
    prime_list = judge_prime(MAX_Q)
    
#    for i in range(MAX_Q+1):
    like2017_list = []
    for prime in prime_list:
        if (prime+1)/2 in prime_list:
            like2017_list.append(prime)
            
    
    # judge
    for i in range(Q):
        print(sum([LR[i][0]<=like2017 <= LR[i ][1] for like2017 in like2017_list]))


    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import math as m

def judge_prime(num):
    isPrime = [True]*(num+1)
    isPrime[0] = False
    isPrime[1] = False
    border = m.sqrt(num)
    i = 2
    while i <= border:
        if isPrime[i]:
            j = i*2
            while j <= num:
                isPrime[j] = False
                j += i
        i += 1
        
    #prime_list = []
    like2017_list = []
    for prime in range(3,num+1,2):
#        if isPrime[prime]:
#            prime_list.append(prime)
        if isPrime[int(prime)] and isPrime[int((prime+1)/2)]:
            like2017_list.append(prime)
        
    return like2017_list
        
    
    
def main():
    #input
#    Q1 = 1
#    LR1 = [[3,7]]
#    
#    Q2 = 4
#    LR2 = [[13, 13],
#                [7, 11],
#                [7, 11],
#                [2017, 2017]]
#    
#    
#    Q = Q2
#    LR = LR2
    
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, input().split())))

    # 1. find 2017-like number
    MAX_Q = 10**5
    
    like2017_list = judge_prime(MAX_Q)

    
    # judge
    csum = [0]*(MAX_Q+1)
    i = 0
    cnt = 0
    for like2017 in like2017_list:
        while i < like2017:
            csum[i] = cnt
            i += 1
        cnt += 1
    for i in range(like2017_list[-1], MAX_Q+1):
        csum[i] = cnt
        
    
    for i in range(Q):
        print(csum[LR[i][1]] - csum[LR[i][0]-1])


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

n = int(input())
l = map(int, input().split())
ans = []
for i in l:
  ans.append(i)
  ans = ans[::-1]

print(*ans)

### FIXED CODE ###

from collections import deque
n = int(input())
l = map(int, input().split())
ans = deque()
for idx, v in enumerate(l):
  if idx % 2 == 0:
    ans.append(v)
  else:
    ans.appendleft(v)
if len(ans) % 2 == 1:
  ans.reverse()
            
print(*ans)
### BUGGY CODE ###

N = int(input())
H_list = input().split(" ")
max_count = 0
for i in range(0, N):
    S = int(H_list[i])
    count = 0
    for j in range(i + 1, N):
        if S >= int(H_list[j]):
            S = int(H_list[j])
            count += 1
        else:
            break
    if max_count < count:
        max_count = count
    if max_count >= N - i:
        break
    if max_count >= N / 2:
        break
print(max_count)

### FIXED CODE ###

N = int(input())
H_LIST = input().split(" ")
H = []

for i in H_LIST:
    H.append(int(i))
   
count = 0
max_count = 0
for i in range(0, N-1):
    if H[i] >= H[i + 1]:
        count += 1
    else:
        count = 0 #メモリの動き
        
    if max_count < count:
        max_count = count


print(max_count)
### BUGGY CODE ###

    # -*- coding: utf-8 -*-
def main():
    N = int(input())
    D = list(map(int,input().split()))
    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            ans += D[i]^D[j]

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

if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = list(map(int, input().split()))
    A = np.array(A, np.int64)
    ans = 0
    for i in range(60):
        bit = np.count_nonzero(A & 1)
        ans += bit * (N - bit) * (2 ** i)
        ans %= mod
        A >>= 1
    print(ans)

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

# -*- coding: utf-8 -*-
r, g, b, n = map(int, input().split())

ans = 0
max_r = n // r

for i in range(max_r+1):
    tmp = n - (r * i)
    max_g = tmp // g
    after_r = tmp
    for j in range(max_g+1):
        tmp = after_r
        tmp = tmp - (g * j)
        max_b = tmp // b
        after_g = tmp
        if tmp%b == 0:
            ans = ans + 1

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
in_r, in_g, in_b, n = map(int, input().split())

ans = 0

in_list= [in_r,in_g,in_b]
sorted_list = sorted(in_list)

r = sorted_list[-1]
g = sorted_list[-2]
b = sorted_list[-3]

max_r = n // r

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

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

from collections import deque


h, w = map(int, input().split())
Ch, Cw = map(lambda x: int(x)-1, input().split())
Dh, Dw = map(lambda x: int(x)-1, input().split())
dy, dx = (-1, 0, 1, 0), (0, -1, 0, 1)
maze = [[float('inf') if x == '.' else -float('inf') for x in input()] for _ in range(h)]
maze[Ch][Cw] = 0
que = deque()
que.append((0, Ch, Cw))
while que:
    c, y, x = que.popleft()
    
    if y == Dh and x == Dw:
        break
    
    if c > maze[y][x]:
        continue
    
    for i in range(4):
        y2, x2 = y + dy[i], x + dx[i]
        if 0 <= y2 < h and 0 <= x2 < w and c < maze[y2][x2]:
            maze[y2][x2] = c
            que.appendleft((c, y2, x2))
            
        for j in range(-2, 3):
            for k in range(-2, 3):
                y3, x3, c2 = y + j, x + k, c+1
                if 0 <= y3 < h and 0 <= x3 < w and c2 < maze[y3][x3]:
                    maze[y3][x3] = c2
                    que.append((c2, y3, x3))

ans = maze[Dh][Dw]
if ans == float('inf'):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

from collections import deque


h, w = map(int, input().split())
Ch, Cw = map(lambda x: int(x)-1, input().split())
Dh, Dw = map(lambda x: int(x)-1, input().split())
dy, dx = (-1, 0, 1, 0), (0, -1, 0, 1)
maze = [[float('inf') if x == '.' else -float('inf') for x in input()] for _ in range(h)]
maze[Ch][Cw] = 0
que = deque()
que.append((0, Ch, Cw))
while que:
    c, y, x = que.popleft()
    
    if c > maze[y][x]:
        continue
    
    if y == Dh and x == Dw:
        break
    
    for i in range(4):
        y2, x2 = y + dy[i], x + dx[i]
        if 0 <= y2 < h and 0 <= x2 < w and c < maze[y2][x2]:
            maze[y2][x2] = c
            que.appendleft((c, y2, x2))
            
    for i in range(-2, 3):
        for j in range(-2, 3):
            y3, x3, c2 = y + i, x + j, c+1
            if 0 <= y3 < h and 0 <= x3 < w and c2 < maze[y3][x3]:
                maze[y3][x3] = c2
                que.append((c2, y3, x3))

ans = maze[Dh][Dw]
if ans == float('inf'):
    print(-1)
else:
    print(ans)