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

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d=[float("inf")]*n #各頂点への距離
    used=[False]*n
    d[s]=0
    
    while True:
        v=-1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v==-1): #その頂点が使われたかチェック
                v=i			            #まだなら仮確定
            elif (not used[i]) and d[i]<d[v]: #より距離が近いのがあればそちらから
                v=i
        if v==-1:
             break
        used[v]=True
               
        for j in range(n):
            d[j]=min(d[j],d[v]+cost[v][j])
    return d

################################
n=int(input()) #n:頂点数　w:辺の数
w=n-1

cost=[[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w):
    x,y,z=map(int,input().split())
    cost[x-1][y-1]=z
    cost[y-1][x-1]=z
length=(dijkstra(0,n,w,cost))

for i in length:
    if i%2==0:
        print(0)
    else:
        print(1)

### FIXED CODE ###

import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d
################################
n=int(input()) #:頂点数　w:辺の数
w=n-1
edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1]) 

for i in dijkstra_heap(0,edge):
    if i%2==0:
        print(0)
    else:
        print(1)
### BUGGY CODE ###

N, P=map(int,input().split())
S = list(map(int,list(input())))
def ma():
  dp = [0]*P
  ret = 0
  for i in range(N):
    dp_ = [0]*P
    b = S[i]%P
    for j in range(P):
      dp_[(j*10+b)%P] += dp[j]
    dp_[b] += 1
    ret += dp_[0]
    dp = dp_[:]
  print(ret)    
ma()

### FIXED CODE ###

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

def ma25():
  ret = 0
  for i in range(N):
    if S[i]%P == 0:
      ret+=(i+1)
  print(ret)

def ma():
  dp = [0]*P
  dp[0] = 1
  r = 0
  for i in range(N-1,-1,-1):
    r = ((S[i]*pow(10,N-1-i,P))+r)%P
    dp[r] += 1
  ret = 0
  for m in dp:
    ret += m*(m-1)//2
  print(ret)

if P == 2 or P == 5:
  ma25()
else:
  ma()
### BUGGY CODE ###

import re

_, Q = [int(x) for x in input().split()]
S = input()
ac = re.compile('AC')

results = []
for i in range(Q):
    l, r = [int(x) for x in input().split()]
    target = S[l-1:r]
    results.append(len(ac.findall(target)))

for i in results:
    print(i)


### FIXED CODE ###

N, Q = [int(x) for x in input().split()]
S = input()

t = [0] * (N + 1)

for i in range(N):
    if S[i:i+2] == 'AC':
        t[i+1] = t[i] + 1
    else:
        t[i+1] = t[i]

for i in range(Q):
    l, r = [int(x) for x in input().split()]
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N=int(input())

P=list(map(float,input().split()))

dp=[[0 for i in range(N+1)] for j in range(N+1)]
dp[0][0]=1

for i in range(N):
    for j in range(N-i):
        dp[i+1][j]+=dp[i][j]*P[i+j]
        dp[i][j+1]+=dp[i][j]*(1-P[i+j])        

ans=0
start=(N+1)//2
j=0
for i in range(start,N+1)[::-1]:
    ans+=dp[i][j]
    j+=1
print(ans)
#print(dp)




### FIXED CODE ###

# coding: utf-8
# Your code here!
N=int(input())
P=list(map(float,input().split()))

dp=[[0]*(N+1) for i in range(N+1)]

dp[0][0]=1
for n in range(N):
    for i in range(n+1):
        j=n-i
        dp[j][i+1]+=dp[j][i]*P[n]
        dp[j+1][i]+=dp[j][i]*(1-P[n])

ans=0
for i in range((N+1)//2):
    ans+=dp[i][-i-1]

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

(n, m) = list(map(int, input().split()))
p = list(map(int, input().split()))
pairs = []
for i in range(0, m):
    pairs.append(list(map(int, input().split())))
cG = []
for e in pairs:
    aru = False
    do = []
    for c in cG:
        if e[0] in c or e[1] in c:
            if not do == []:
                mix = do + c
                cG.remove(do)
                cG.remove(c)
                cG.append(mix)
                break
            else:
                do = c
        if e[0] in c:
            aru = True
            c.append(e[1])
        if e[1] in c:
            aru = True
            c.append(e[0])
    if not aru:
        cG.append(e)

cant = []
for i in range(1, n + 1):
    cc = False
    for c in cG:
        if i in c:
            cc = True
            break
    if not cc:
        cant.append(i)

res = 0
for c in cG:
    for i in range(1, n + 1):
        if i in c:
            ku = p.index(i) + 1
            if ku in c:
                res = res + 1

for i in cant:
    if p[i - 1] == i:
        res = res + 1
print(res)


### FIXED CODE ###

def ge(x):
    return int(x) - 1


(n, m) = tuple(map(int, input().split()))
inp = list(map(ge, input().split()))
arr = [i for i in range(n)]


def root(a):
    global arr
    if arr[a] == a:
        return a
    else:
        tmp = root(arr[a])
        arr[a] = tmp
        return tmp


def sameroot(x, y):
    return root(x) == root(y)


def merge(x, y):
    global arr
    if not sameroot(x, y):
        arr[root(y)] = root(x)


for i in range(m):
    merge(*tuple(map(ge, input().split())))

res = 0
for i in range(n):
    if sameroot(i, inp[i]):
        res += 1
print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = [int(input()) for i in range(N)]

b = sorted(a)
for i in range(N):
    if i == a.index(max(a)):
        print(b[-2])
    else:
        print(b[-1])

### FIXED CODE ###

n=int(input())
a = [int(input()) for i in range(n)]
b = sorted(a)
for i in a:
    print(b[-2] if i==b[-1] else b[-1])
### BUGGY CODE ###

N = int(input())
S = list(int(i) for i in input().split())  
list = []
count = 0

for i in range(N):
    if S[i] not in list:
        num = S.count(S[i])
        if num < S[i]:
            count += S.count(S[i])
        elif num > S[i]:
            count += (num-S[i])
    list.append(S[i])

print(count)

### FIXED CODE ###

N = int(input())
S = list(int(i) for i in input().split())  
dict = {}
count = 0

for i in range(N):
    if S[i] not in dict:
        dict[S[i]] = 1
    else:
        dict[S[i]] += 1

for key, value in dict.items():
    if key < value:
        count += (value-key)
    elif key > value:
        count += value

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

mod = 1000000007
import collections
n, m = map(int, input().split())
dat_m = []
dp = collections.deque([])
for i in range(m):
    dat_m.append(int(input()))
dp.append(1)
for i in range(1, n + 1):
    t = 0
    t = dp[i - 1]
    if i > 1:
        t += dp[i - 2]
    if i in dat_m:
        t = 0
    t = t % mod
    dp.append(t)

print(dp[n])

### FIXED CODE ###

mod = 1000000007
n, m = map(int, input().split())
dat_m = []
dp = [0] * (n + 1)
for i in range(m):
    t = int(input())
    dp[t] = -1

dp[0] = 1
for i in range(1, n + 1):
    if dp[i] == -1:
        dp[i] = 0
        continue
    dp[i] = dp[i - 1]
    if i > 1:
        dp[i] += dp[i - 2]
    if i in dat_m:
        dp[i] = 0
    dp[i] = dp[i] % mod

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

n,k=map(int,input().split())
l=list(map(int,input().split()))
dp=[0]*n
dp[0]=0
for i in range(1,n):
    s=min(k,i)+1
    ans=dp[i-1]+abs(l[i]-l[i-1])
    for j in range(2,s):
        ans=min(ans,dp[i-j]+abs(l[i]-l[i-j]))
    dp[i]=ans
print(dp[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
dp=[0]*n
dp[0]=0
for i in range(1,n):
    s=min(k,i)+1
    ans=dp[i-1]+abs(l[i]-l[i-1])
    for j in range(2,s):
        ans=min(ans,dp[i-j]+abs(l[i]-l[i-j]))
    dp[i]=ans
print(dp[n-1])
### BUGGY CODE ###

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

cnt=0
ans=[]
ans.append(A[0])
ans.append(A[1])
cnt+=ans[0]
for i in range(2,N):
    k=ans.index(A[int((i-1)/2)])
    if k==len(ans)-1:
        kb=k-1
        kn=0
    else:
        kb=k-1
        kn=k+1

    if ans[kb]>=ans[kn]:
        cnt+=min(ans[k],ans[kb])
        ans.insert(kb,A[i])
    elif ans[kb]<ans[kn]:
        cnt+=min(ans[k],ans[kn])
        ans.insert(kn,A[i])

print(cnt)

### FIXED CODE ###

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

ans=0
for i in range(1,N):
    ans+=A[N-int(i/2)]

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

from collections import deque

n, m = map(int, input().split())
a_list = list(map(int, input().split()))
m_list = []
cnt = 0
for _ in range(m):
    b, c = map(int, input().split())
    m_list += [c]*b
    cnt += b
a_list.sort()
m_list.sort(reverse=True)
m_q = deque(m_list)
ans = 0
check = m_q.popleft()
for a in a_list:
    if a < check:
        ans += check
        if cnt <= 1:
            check = 0
        else:
            check = m_q.popleft()
            cnt -= 1
    else:
        ans += a
print(ans)


### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
a_list = list(map(int, input().split()))
m_list = []
for _ in range(m):
    b, c = map(int, input().split())
    m_list.append([c, b])
m_list.sort(reverse=True)
cnt = 0
tmp_list = []
for c, b in m_list:
    if cnt < n:
        tmp_list += [c]*b
    else:
        break
    cnt += b
a_list.extend(tmp_list)
a_list.sort(reverse=True)
print(sum(a_list[:n]))
### BUGGY CODE ###

import sys
import math
from collections import deque
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami2(n, cnt):
  if n == v:
    return
  choku_visited[n] = True
  if cnt <= aoki[n]:
    choku[n] = cnt
    for x in edge[n]:
      if choku_visited[x] == False:
        tami2(x, cnt+1)

N, u, v = IL()
ab = [IL() for _ in range(N-1)]

aoki = [0]*(N+1)
aoki_visited = [False]*(N+1)
choku = [0]*(N+1)
choku_visited = [False]*(N+1)

edge = [[] for _ in range(N+1)]
for a,b in ab:
  edge[a].append(b)
  edge[b].append(a)

d = deque([[v,0]])
while d:
  n,cnt = d.popleft()
  aoki_visited[n] = True
  aoki[n] = cnt
  for x in edge[n]:
    if aoki_visited[x] == False:
      d.append([x, cnt+1])

tami2(u, 0)
#print(aoki)
#print(choku)

ans = 0
for i in range(N+1):
  if choku[i] == 0 and i != u:
    continue
  if aoki[i] > choku[i]:
    ans = max(ans, aoki[i] - 1)

print(ans)

### FIXED CODE ###

import sys
import math
from collections import deque
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, u, v = IL()
ab = [IL() for _ in range(N-1)]

aoki = [0]*(N+1)
aoki_visited = [False]*(N+1)
choku = [0]*(N+1)
choku_visited = [False]*(N+1)

edge = [[] for _ in range(N+1)]
for a,b in ab:
  edge[a].append(b)
  edge[b].append(a)

d = deque([[v,0]])
while d:
  n,cnt = d.popleft()
  aoki_visited[n] = True
  aoki[n] = cnt
  for x in edge[n]:
    if aoki_visited[x] == False:
      d.append([x, cnt+1])

dd = deque([[u,0]])
while dd:
  n,cnt = dd.popleft()
  choku_visited[n] = True
  if cnt <= aoki[n]:
    choku[n] = cnt
  for x in edge[n]:
    if choku_visited[x] == False:
      dd.append([x, cnt+1])

#print(aoki)
#print(choku)

ans = 0
for i in range(N+1):
  if choku[i] == 0 and i != u:
    continue
  if aoki[i] > choku[i]:
    ans = max(ans, aoki[i] - 1)

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

import numpy as np
def main():
  N,W = map(int,input().split())  #nは入力回数
  num_list = [list(map(int, input().split())) for _ in range(N)]
  dp=np.zeros((N+1,W+1))
  weight=[row[0] for row in num_list]
  value=[row[1] for row in num_list]
  for i in range(0,N):
    for sum_w in range(0,W+1):
      if(sum_w-weight[i]>=0):
        dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-weight[i]]+value[i])
      #iを選ばない場合
      dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w])
  print(int(dp[N][W]))
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
  N,W = map(int,input().split())  #nは入力回数
  num_list = [list(map(int, input().split())) for _ in range(N)]
  dp = [[0] * (W+1) for i in range(N+1)]
  weight=[row[0] for row in num_list]
  value=[row[1] for row in num_list]
  for i in range(0,N):
    for sum_w in range(0,W+1):
      if(sum_w-weight[i]>=0):
        dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-weight[i]]+value[i])
      #iを選ばない場合
      dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w])
  print(int(dp[N][W]))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import deque
from copy import deepcopy, copy
dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]
N = 3
def MAIN():
    MAP = tuple(sum([input().split() for _ in range(N)], []))
    y0, x0 = divmod(MAP.index("0"), N)
    goal = ('1', '2', '3', '4', '5', '6', '7', '8', '0')
    ans = 0
    dp = deque([[y0, x0, 0, MAP]])
    LOG = {MAP}
    while dp:
        y, x, cnt, M = dp.popleft()
        if M == goal:
            print(cnt)
            break
        cnt += 1
        yx = y * N + x
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < N and 0 <= nx < N:
                CM = list(deepcopy(M))
                nyx = ny * N + nx
                CM[yx], CM[nyx] = CM[nyx], CM[yx]
                CM = tuple(CM)
                if not CM in LOG:
                    dp.append([ny, nx, cnt, CM])
                    LOG.add(CM)
MAIN()



### FIXED CODE ###

from collections import deque
N = 3
m = {8: {7, 5}, 7: {8, 6, 4}, 6: {7, 3}, 5: {8, 4, 2}, 4: {7, 5, 3, 1}, 3: {6, 4, 0}, 2: {5, 1}, 1: {4, 2, 0},
     0: {3, 1}}
goal = 123456780
def g(i, j, a):
    t = a // (10 ** j) % 10
    return a - t * (10 ** j) + t * (10 ** i)
def solve():
    MAP = "".join(input().replace(" ", "") for _ in range(N))
    zero = 8 - MAP.find("0")
    start = int(MAP)
    if start == goal:
        return 0
    dp = deque([(0, start, zero, 1), (0, goal, 0, 0)])
    TABLE = {start: (1, 0), goal: (0, 0)}
    while dp:
        cnt, M, yx, flg = dp.popleft()
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                if TABLE[key][0] != flg:
                    return TABLE[key][1] + cnt
                continue
            TABLE[key] = (flg, cnt)
            dp.append((cnt, key, nyx, flg))
def MAIN():
    print(solve())
MAIN()
### BUGGY CODE ###

s = list(input())
len_s = len(s)
list_2019 = ['2019', '4038', '6057', '8076', '10095', '12114', '14133', '16152', '18171', '20190', '22209', '24228',
             '26247', '28266', '30285', '32304', '34323', '36342', '38361', '40380', '42399', '44418', '46437',
             '48456', '50475', '52494', '54513', '56532', '58551', '60570', '62589', '64608', '66627', '68646',
             '70665', '72684', '74703', '76722', '78741', '80760', '82779', '84798', '86817', '88836', '90855',
             '92874', '94893', '96912', '98931', '100950', '102969', '104988', '107007', '109026', '111045',
             '113064', '115083', '117102', '119121', '121140', '123159', '125178', '127197', '129216', '131235',
             '133254', '135273', '137292', '139311', '141330', '143349', '145368', '147387', '149406', '151425',
             '153444', '155463', '157482', '159501', '161520', '163539', '165558', '167577', '169596', '171615',
             '173634', '175653', '177672', '179691', '181710', '183729', '185748', '187767', '189786', '191805',
             '193824', '195843', '197862', '199881']
ans = 0
for i in range(1, len_s + 1):
    for j in range(len_s):
        if j + i <= len_s:
            if ''.join(s[j:j + i]) in list_2019:
                ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
s = input()[::-1]
cnt = [0]
d = 0
mod = 2019

for i in s:
    tmp = int(i) * pow(10, d, mod) % mod
    tmp = cnt[-1] + tmp
    cnt.append(tmp % mod)
    d += 1

cnt = Counter(cnt)
ans = sum(j * (j - 1) // 2 for j in cnt.values())
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
lst=[]
print_lst=[]
for i in range(n):
    lst.append([])
for i in range(m):
    p,y=map(int,input().split())
    lst[p-1].append(y)
    print_lst.append([p-1,y])

for i in range(n):
    lst[i]=sorted(lst[i])

for i in range(m):
    left=str(print_lst[i][0]+1)
    right=str(lst[print_lst[i][0]].index(print_lst[i][1])+1)
    prnt=["0"*(6-len(left)),left,"0"*(6-len(right)),right]
    print("".join(prnt))

### FIXED CODE ###

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
lst=[]
for i in range(n):
    lst.append([])

for i in range(m):
    p,y=map(int,input().split())
    lst[p-1].append([i,p,y])

for i in range(n):
    lst[i]=sorted(lst[i],key=lambda x:x[2])

for i in range(n):
    for j in range(len(lst[i])):
        lst[i][j].append(j+1)

lst=[i for j in lst for i in j]
lst=sorted(lst,key=lambda x:x[0])

for i in range(m):
    left=str(lst[i][1])
    right=str(lst[i][3])
    prnt=["0"*(6-len(left)),left,"0"*(6-len(right)),right]
    print("".join(prnt))
### BUGGY CODE ###

def main():
	H, W = map(int, input().split())
	S = [""]*H
	visit = [[False for _ in range(W)] for _ in range(H) ]
	for i in range(H):
		S[i] = input()

	stack = []
	for i in range(H):
		for j in range(W):
			if visit[i][j]:
				continue
			stack.append([i, j])
			while stack:
				current = stack.pop()
				if S[current[0]][current[1]] == ".":
					continue

				if current[1] < W-1 and S[current[0]][current[1]+1] == "#":
					stack.append([current[0], current[1]+1])
					visit[current[0]][current[1]+1] = True
					visit[current[0]][current[1]] = True
				if current[0] < H-1 and S[current[0]+1][current[1]] == "#":
					stack.append([current[0]+1, current[1]])
					visit[current[0]+1][current[1]] = True
					visit[current[0]][current[1]] = True

			if S[i][j] == "#" and not visit[i][j]:
				print("No")
				return

	print("Yes")


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
	H, W = map(int, input().split())
	S = [""]*H
	for i in range(H):
		S[i] = input()

	for i in range(H):
		for j in range(W):
			if S[i][j] == ".":
				continue
			if (
				(i > 0 and S[i-1][j] == "#")
				or (j > 0 and S[i][j-1] == "#")
				or (i < H-1 and S[i+1][j] == "#")
				or (j < W-1 and S[i][j+1] == "#")
				):
				continue
			print("No")
			return

	print("Yes")


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

N=int(input())
Vn=list(map(int,input().split()))
Cn=list(map(int,input().split()))

best = 0
for i in range(2**N):
    t = 0
    for j in range(N):
        if (i >> j) & 1:
            t += (Vn[j] - Cn[j])
    if t > best:
        best = t
print(best)


### FIXED CODE ###

N=int(input())
Vn=list(map(int,input().split()))
Cn=list(map(int,input().split()))

best = 0
for i in range(2**N):
    t = 0
    for j in range(N):
        if (i >> j) & 1:
            t += (Vn[j] - Cn[j])
    if t > best:
        best = t
print(best)
### BUGGY CODE ###


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

D = []

for i in range(C):

    d = list(map(int,input().split()))

    D.append(d)

c = []

for i in range(N):

    cc = list(map(int,input().split()))
    c.append(cc)


ans = float("inf")


for c1 in range(C):

    c1 += 1

    for c2 in range(C):

        c2 += 1

        for c3 in range(C):

            c3 += 1

            


            if c1 == c2 or c2 == c3 or c3 == c1:
                continue;

            now = 0

            for i in range(N):

                for j in range(N):


                    if (i + j) % 3 == 0 and c[i][j] != c1:

                        now += D[c[i][j]-1][c1-1]

                    elif (i + j) % 3 == 1 and c[i][j] != c2:

                        now += D[c[i][j]-1][c2-1]

                    elif (i + j) % 3 == 2 and c[i][j] != c3:

                        now += D[c[i][j]-1][c3-1]

            ans = min(ans,now)


print (ans)


### FIXED CODE ###


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

D = []

for i in range(C):

    d = list(map(int,input().split()))

    D.append(d)

c = []

for i in range(N):

    cc = list(map(int,input().split()))
    c.append(cc)


lis1 = []
lis2 = []
lis3 = []

for c1 in range(C):

    c1 += 1

    now = 0

    for i in range(N):

        for j in range(N):

            if (i + j) % 3 == 0 and c[i][j] != c1:

                now += D[c[i][j]-1][c1-1]

    lis1.append(now)


for c2 in range(C):

    c2 += 1

    now = 0

    for i in range(N):

        for j in range(N):

            if (i + j) % 3 == 1 and c[i][j] != c2:

                now += D[c[i][j]-1][c2-1]

    lis2.append(now)


for c3 in range(C):

    c3 += 1

    now = 0

    for i in range(N):

        for j in range(N):

            if (i + j) % 3 == 2 and c[i][j] != c3:

                now += D[c[i][j]-1][c3-1]

    lis3.append(now)


ans = float("inf")

for i in range(C):

    for j in range(C):

        for k in range(C):


            if i == j or j == k or k == i :
                continue;

            ans = min(ans,lis1[i] + lis2[j] + lis3[k])

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

H, W, M = map(int, input().split())
h_list = [0] * H
w_list = [0] * W
target = []
for _ in range(M):
  h, w = map(int, input().split())
  h_list[h-1] += 1
  w_list[w-1] += 1
  target += [[h-1,w-1]]

h_max = max(h_list)
w_max = max(w_list)
h_max_list = [i for i, v in enumerate(h_list) if v == max(h_list)]
w_max_list = [i for i, v in enumerate(w_list) if v == max(w_list)]

place = len(h_max_list) * len(w_max_list)
candidate = 0
for h,w in target:
  if (h in h_max_list) and (w in w_max_list):
    candidate +=1

print(h_max+w_max-(place == candidate))

### FIXED CODE ###

H, W, M = map(int, input().split())
h_list = [0] * H
w_list = [0] * W
target = []
for _ in range(M):
  h, w = map(int, input().split())
  h_list[h-1] += 1
  w_list[w-1] += 1
  target += [[h-1,w-1]]

h_max = max(h_list)
w_max = max(w_list)
h_max_list = set([i for i, v in enumerate(h_list) if v == h_max])
w_max_list = set([i for i, v in enumerate(w_list) if v == w_max])

place = len(h_max_list) * len(w_max_list)
candidate = 0
for h,w in target:
  if (h in h_max_list) and (w in w_max_list):
    candidate +=1

print(h_max+w_max-(place == candidate))
### BUGGY CODE ###

I=lambda:map(int,input().split())
R,G,B,N=I()
r=0
for i in range(N//R+1):
    for j in range(N//G+1):
        if N-i*R-j*G>=0 and (N-i*R-j*G)%B==0:
            r+=1
#            print(i,j,N-i-j)
print(r)

### FIXED CODE ###

I=lambda:map(int,input().split())
R,G,B,N=I()
r=0
for i in range(N//R+1):
    for j in range(N//G+1):
        if N-i*R-j*G>=0 and (N-i*R-j*G)%B==0:
            r+=1
print(r)