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

def abc164_d():
  s = str(input())
  ans = 0
  for i in range(len(s)-4):
    for j in range(i+4, len(s)+1):
      t = int(s[i:j])
      if t % 2019 == 0:
        ans += 1
  print(ans)

abc164_d()

### FIXED CODE ###

def abc164_d():
    # 解説放送
    s = str(input())
    n = len(s)
    m = 2019
    srev = s[::-1]  # 下の位から先に見ていくために反転する
    x = 1  # 10^i ??
    total = 0  # 累積和 (mod 2019 における累積和)
    cnt = [0] * m  # cnt[k] : 累積和がkのものが何個あるか
    ans = 0
    for i in range(n):
        cnt[total] += 1
        total += int(srev[i]) * x
        total %= m
        ans += cnt[total]
        x = x*10 % m
    print(ans)

abc164_d()
### BUGGY CODE ###

N, W = map(int, input().split(" "))
#items = [tuple(map(int, input().split(" "))) for _ in range(N)]
dp = [[0]*(W+1) for i in range(N+1)]

for i in range(1, N+1):
    w, v = map(int, input().split(" "))
    for j in range(1, W+1):
        if j >= w:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split(" "))
#items = [tuple(map(int, input().split(" "))) for _ in range(N)]
dp = [[0]*(W+1) for i in range(N+1)]

for i in range(1, N+1):
    w, v = map(int, input().split(" "))
    for j in range(1, W+1):
        if j >= w:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
        else:
            dp[i][j] = dp[i-1][j]

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

import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())

    # dp[i][U] : 男 i 番目まで見た時、埋まっている女性の state が U の場合の数
    # i = U.popcount なので i を持つ必要はない
    dp = [None] * (1 << n)
    dp[0] = 1
    now = [0]
    for _ in range(n):
        A = list(map(int, input().split()))
        next = []
        for i in range(n):
            if not A[i]:
                continue
            for U in now:
                if (U >> i) & 1:
                    continue
                nU = U | 1 << i
                if dp[nU] is None:
                    dp[nU] = dp[U]
                    next.append(nU)
                else:
                    dp[nU] += dp[U]
                    if dp[nU] >= MOD:
                        dp[nU] -= MOD
        now = next

    res = dp[-1]
    if res is None:
        res = 0
    print(res)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    popcount_to_state = [[] for _ in range(n + 1)]
    for U in range(1 << n):
        popcount_to_state[bin(U).count('1')].append(U)

    dp = [0] * (1 << n)
    dp[0] = 1
    for i in range(n):
        A = tuple(map(int, input().split()))
        for j in range(n):
            if not A[j]:
                continue
            for U in popcount_to_state[i]:
                if (U >> j) & 1:
                    continue
                nU = U | 1 << j
                dp[nU] += dp[U]
                if dp[nU] >= MOD:
                    dp[nU] -= MOD
    print(dp[-1])
resolve()
### BUGGY CODE ###

from fractions import gcd

lcm = lambda a, b: a * b // gcd(a, b)
mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

L = 1
for a in A:
    L = lcm(L, a)

ans = 0
for a in A:
    ans = (ans + L // a) % mod

print(ans)


### FIXED CODE ###

from fractions import gcd
from functools import reduce

def main():
    lcm = lambda a, b: a * b // gcd(a, b)
    mod = 10 ** 9 + 7

    N, *A = map(int, open(0).read().split())

    L = reduce(lcm, A)
    print(sum(L // a for a in A) % mod)

main()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    dp = [[0] * n for _ in range(n)]
    coff = 1 if n % 2 else -1
    for i, a in enumerate(aa):
        dp[i][i] = coff * a
    # p2D(dp)
    for d in range(1, n):
        coff *= -1
        for l in range(n - 1):
            r = l + d
            if r >= n: break
            if coff == 1:
                dp[l][r] = max(dp[l + 1][r] + aa[l], dp[l][r - 1] + aa[r])
            else:
                dp[l][r] = min(dp[l + 1][r] - aa[l], dp[l][r - 1] - aa[r])
    # p2D(dp)
    print(dp[0][-1])

main()


### FIXED CODE ###

def kukan(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            L = a[i] - dp[i + 1][j]
            R = a[j] - dp[i][j - 1]
            dp[i][j] = L if L > R else R
    return dp[0][n - 1]


n = int(input())
a = list(map(int, input().split()))
print(kukan(n, a))
### BUGGY CODE ###


def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for i in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = dp_table(N, sum_A + 1)
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

    # init
    dp[0][A[0]] = 1
    dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

    # init2
    dp2 = dp_table(N, sum_A+1)  # ある二色でsum_Aを等分するパターンを数える
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  # 今度は片方に集中したパターン

    # dp
    sum_now = A[0]
    for i in range(1, N):
        a = A[i]
        sum_now += a
        for length in range(0, sum_now+1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            if length >= a:
                dp[i][length] = (dp[i - 1][length - a] +
                                 dp[i - 1][length] * 2) % mod
            else:
                dp[i][length] = dp[i-1][length]*2

        for length in range(min(sum_now + 1, sum_A // 2 + 1)):
            if length >= a:
                dp2[i][length] = (dp2[i - 1][length - a] +
                                  dp2[i - 1][length]) % mod
            else:
                dp2[i][length] = dp2[i-1][length]

    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###


def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for _ in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = [[0] * (sum_A+1) for i in range(N)]
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

    # init
    dp[0][A[0]] = 1
    dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

    # init2
    dp2 = [[0] * (sum_A+1) for i in range(N)]  # ある二色でsum_Aを等分するパターンを数える
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  # 今度は片方に集中したパターン

    # dp
    sum_now = A[0]
    for i in range(1, N):
        a = A[i]
        sum_now += a
        for length in range(sum_now+1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            if length >= a:
                dp[i][length] = dp[i - 1][length - a] + \
                    (dp[i - 1][length] << 1)
            else:
                dp[i][length] = dp[i-1][length] << 1
            dp[i][length] %= mod

        for length in range(min(sum_now + 1, sum_A // 2 + 1)):
            if length >= a:
                dp2[i][length] = dp2[i - 1][length - a] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            dp2[i][length] %= mod
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


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

n = int(input())
ans = 1
for i in range(1,n+1):
    ans*=i
print(ans%(1000000007))

### FIXED CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
    ans = (ans*i)%1000000007
print(ans)
### BUGGY CODE ###

h, w = map(int, input().split())
s = [input() for _ in range(h)]
sy = [0] * w
ret = 0
for y in range(h):
    seqx = 0
    seqy = 0
    for x in range(w):
        if s[y][x] == '.':
            if sy[x] == 0:
                yy = y
                while yy < h and s[yy][x] != '#':
                    yy += 1
                sy[x] = yy - y
            seqx += 1
            seqy = max(seqy, sy[x])
            ret = max(ret, seqx + seqy - 1)
        else:
            seqx = 0
            seqy = 0
            sy[x] = 0
print(ret)


### FIXED CODE ###

h, w = map(int, input().split())
s = [input() for _ in range(h)]
sy = [0] * w
ret = 0
for y in range(h):
    seqx = 0
    seqy = 0
    for x in range(w):
        if s[y][x] == '.':
            if sy[x] == 0:
                yy = y
                while yy < h and s[yy][x] != '#':
                    yy += 1
                sy[x] = yy - y
            seqx += 1
            seqy = max(seqy, sy[x])
            ret = max(ret, seqx + seqy - 1)
        else:
            seqx = 0
            seqy = 0
            sy[x] = 0
print(ret)
### BUGGY 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 j in range(W - w, -1, -1):
            if dp[j] != -1:
                dp[j + w] = max(dp[j + w], dp[j] + v)
    print(max(dp))


main()


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

#from scipy.misc import comb

K, S = map(int, input().split())
x = S if K>S else K

#a = comb(3*K, S, exact=True)
#print(a)

ans = 0
for i in range(x+1):
  for j in range(x+1):
    for k in range(x+1):
      if i+j+k==S:
        ans += 1
print(ans)

### FIXED CODE ###

K, S = map(int, input().split())
x = S if K>S else K

ans = 0
for i in range(x+1):
  x1 = S-i
  for j in range((K if x1>K else x1)+1):
    if S-i-j <= K:
      ans += 1

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

s=input()
query=int(input())

li_q = []
for _ in range(query):
    li_q.append(input().split())

ans = s
for q in li_q:
    if q[0] == '1':
        ans = ans[::-1]
    else:
        if q[1] == '1':
            ans = q[2] + ans
        else:
            ans = ans + q[2]

print(ans)

### FIXED CODE ###

from collections import deque

s=input()
query=int(input())

li_q = []
for _ in range(query):
    li_q.append(input().split())

rev = False
q_str = deque([s])
for q in li_q:
    if q[0] == '1':
        rev = not rev
    else:
        if q[1] == '1':
            if rev:
                q_str.append(q[2])
            else:
                q_str.appendleft(q[2])
        else:
            if rev:
                q_str.appendleft(q[2])
            else:
                q_str.append(q[2])

li_str = list(q_str)
ans = ''.join(li_str)
if rev:
    ans = ans[::-1]
    
print(ans)
### BUGGY CODE ###

def main():
    s = list(input())
    s = s[::-1]

    l = [[] for i in range(673)]
    l[0].append(0)
    ten = 1
    mod = 673
    now = 0
    for i in range(len(s)):
        now = (now+int(s[i])*ten)%mod
        l[now].append(i+1)
        ten *= 10
    ans = 0
    for i in l:
        if len(i) >= 2:
            for j in range(len(i)-1):
                for k in range(j+1,len(i)):
                    a = sum(list(map(int,s[i[j]:i[k]])))
                    if a %3 == 0:
                        ans += 1
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    s = list(input())
    s = s[::-1]

    l = [[[] for j in range(3)] for i in range(673)]
    l[0][0].append(0)
    mo = 0
    ten = 1
    mod = 673
    now = 0
    ans = 0
    for i in range(len(s)):
        a = int(s[i])*ten
        mo = (mo+a)%3
        now = (now+a)%mod
        if l[now][mo]:
            ans += len(l[now][mo])
        l[now][mo].append(i+1)
        ten *= 10
        ten %= 2019
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# coding:utf-8

n, y = map(int, input().split())
xn = list(map(int, input().split()))

dist_list = list()

for x in xn:
    dist_list.append(abs(y-x))

d_kouho_max = max(dist_list)

for d in reversed(range(d_kouho_max)):
    able = True
    for dist in dist_list:
        if dist%(d+1) == 0:
            pass
        else:
            able = False
            break
    if(able):
        d_max = d+1
        break

print(d_max)


### FIXED CODE ###

# coding:utf-8

from fractions import gcd 

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

dist_list = [abs(x-y) for x in map(int, input().split())]

if n == 1:
    d = dist_list[0]
else:
    d = gcd(dist_list[1], dist_list[0])
    for i in range(n-2):
        d = gcd(d, dist_list[i+1])

print(d)
### BUGGY CODE ###

import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)
S = input()[::-1]
N = len(S)
cnt = [0]*(N+1)
ans = 0
tmp = ''
for i in range(N):
    tmp = S[i] + tmp
    cnt[i] = int(tmp)%2019
cnt2 = [0]*2020
for i in cnt:
    cnt2[i] += 1
for i in cnt2:
    if i >= 2:
        ans += C(i,2)
print(ans)

### FIXED CODE ###

import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)
S = input()[::-1]
N = len(S)
cnt = [0]*(N+1)
ans = 0
keta = 1
for i in range(N):
    cnt[i] = (cnt[i-1] + int(S[i])*keta)%2019
    keta *= 10
    keta %= 2019
cnt2 = [0]*2020
for i in cnt:
    cnt2[i] += 1
for i in cnt2:
    if i >= 2:
        ans += C(i,2)
print(ans)
### BUGGY CODE ###

n=int(input())
x=[n, 0, 0, 0, 0, 0]
a,b,c,d,e=[int(input()) for _ in range(5)]
cnt=0
while x[5] < n:
  x[5]+=min(e,x[4])
  x[4]-=min(e,x[4])
  x[4]+=min(d,x[3])
  x[3]-=min(d,x[3])
  x[3]+=min(c,x[2])
  x[2]-=min(c,x[2])
  x[2]+=min(b,x[1])
  x[1]-=min(b,x[1])
  x[1]+=min(a,x[0])
  x[0]-=min(a,x[0])
  t=x[5]
  cnt+=1
print(cnt)

### FIXED CODE ###

import math
n=int(input())
t=[int(input()) for _ in range(5)]
print(math.ceil(n/min(t))-1+5)
### BUGGY CODE ###

def p_d():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]
    ab = sorted(ab)
    ans = 0

    for i in range(1, m + 1):
        idx = -1
        max_value = -1
        for j in range(len(ab)):
            if ab[j][0] <= i:
                if max_value <= ab[j][1]:
                    max_value = ab[j][1]
                    idx = j
            else:
                break

        if idx != -1:
            ans += max_value
            ab.pop(idx)

    print(ans)


if __name__ == '__main__':
    p_d()


### FIXED CODE ###

from heapq import heappop, heappush


def p_d():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]

    ab.sort()
    ans = 0
    j = 0
    H = []

    for i in range(1, m + 1):
        while j < n and ab[j][0] <= i:
            heappush(H, -ab[j][1])
            j += 1

        if H:
            ans -= heappop(H)

    print(ans)


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

n = int(input())
s = list(map(int, input().rstrip().split(" ")))

min_v = 0
for i in range(0, n):
    v = 0
    for j in range(0, n):
        v = v + abs(s[j] - (s[i]-i + j))
    if i == 0 or v < min_v:
        min_v =v
print(min_v)


### FIXED CODE ###

n = int(input())
s = list(map(int, input().rstrip().split(" ")))

for i in range(0, n):
    s[i] = s[i] - (i+1)
s.sort()

b = s[n//2]

sm = 0
for i in range(0, n):
    sm = sm + abs(s[i] - b)

print(sm)
### BUGGY CODE ###

n,q = list(map(int,input().split()))
s = list(input())
num = list()
check = list()
for i in range(0,n-1):
    if s[i] == "A" and s[i+1] == "C":
        check.append(i+1)
for i in range(0,q):
    num.append(list(map(int,input().split())))
    print(len([k for k in check if k >= num[i][0] and k < num[i][1]]))

### FIXED CODE ###

n,q = list(map(int,input().split()))
s = list(input())
num = list()
check = [0]*n
for i in range(1,n):
        if s[i-1] == "A" and s[i] == "C":
                check[i] = check[i-1]+1
        else:
                check[i] = check[i-1]
ans = 0
for i in range(0,q):
        num = list(map(int,input().split()))
        ans = check[num[1]-1]-check[num[0]-1]
        print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]

graph = [[None] * N for _ in range(N)]
for x, y in edges:
    graph[x - 1][y - 1] = True
    graph[y - 1][x - 1] = True

def dfs(v, c):
    # c: color = 1 or -1
    node[v] = c
    for i, w in enumerate(graph[v]):
        if not w:
            continue

        if node[i] == c:
            return False
        
        if node[i] == 0 and not dfs(i, -c):
            return False
        
    return True

node = [0] * N
if dfs(0, 1):
    x = sum((v + 1) // 2 for v in node)
    print(x * (N - x) - M)
else:
    print(N * (N - 1) // 2 - M)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]

graph = [[] for _ in range(N)]
for x, y in edges:
    graph[x - 1].append(y - 1)
    graph[y - 1].append(x - 1)

def dfs(v, c):
    # c: color = 1 or -1
    node[v] = c
    for i in graph[v]:
        if node[i] == c:
            return False
        
        if node[i] == 0 and not dfs(i, -c):
            return False
        
    return True

node = [0] * N
if dfs(0, 1):
    x = sum(v + 1 for v in node) // 2
    print(x * (N - x) - M)
else:
    print(N * (N - 1) // 2 - M)
### BUGGY CODE ###

def main():
  N = input()
  A= input().split()
  result = False
  for a in A:
    count = A.count(a)
    if count > 1:
      result = True
  if result:
    print("NO")
  else:
    print("YES")

main()

### FIXED CODE ###

def main():
  N = input()
  A=list(map(int, input().split()))
  if len(set(A)) == len(A):
    print("YES")
  else:
    print("NO")

main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
mem=[]

for i in range(n):
	mem.append(a.count(i+1))
	print(mem[i])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
mem=[0]*n

for i in a:
	mem[i-1]+=1

for i in mem:
	print(i)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import combinations
def main():
    n, *a = map(int, read().split())
    large_p = 10 ** 9 + 7
    a2 = [i % large_p for i in a]
    com = tuple(combinations(a2, 2))
    r = 0
    for come in com:
        r += (come[0] * come[1]) % large_p
        r = r % large_p
    print(r)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import accumulate
def main():
    n, *a = map(int, read().split())
    large_p = 10 ** 9 + 7
    aac = tuple(accumulate(a))
    r = 0
    for i1 in range(n):
        t1 = aac[-1] - aac[i1]
        r += (t1 * a[i1]) % large_p
    r = r % large_p
    print(r)


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

m = input()
S = [[1]*m for i in range(m)]
for i in range(input()):
	x,y = map(int,raw_input().split())
	S[y-1][x-1] = 0
	for j in range(m):
		if S[x-1][j] == 0: S[y-1][j] = 0
		if S[j][y-1] == 0: S[j][x-1] = 0
R = [sum(S[i]) for i in range(m)]
C = [sum([S[j][i] for j in range(m)]) for i in range(m)]
while sum(R) + sum(C) > m*(m+1):
	for r in range(m):
		if R.count(R[r]) == 1: continue
		for c in range(m):
			if S[r][c] == 0 and C.count(C[c]) == 1: continue
			if r != c and  R[r] + C[r] > m+1 and R[c] + C[c] > m+1:
				S[r][c] = 0
				R[r] -= 1
				C[c] -= 1
				break
rank = sorted([[C[i],i+1] for i in range(m)])
for r,i in rank: print i

### FIXED CODE ###

def solve(a):
	for i in M-set(a):
		if any(x == i and y not in a for x,y in xy): continue
		r = solve([i]+a)
		if r: return r
	return a
m = input()
M = set(range(1,m+1))
xy = [map(int,raw_input().split()) for i in range(input())]
for i in solve([]): print i
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = -float('inf')
for i in range(n):
    s = []
    j = p[i]-1 
    s.append(c[j])
    while j != i:
        j = p[j]-1
        s.append(s[-1]+c[j])
    l = len(s)
    if k <= l:
        a = max(s[:k])
    elif s[-1] <= 0:
        a = max(s)
    else:
        w, r = divmod(k, l)
        a1 = s[-1]*(w-1) + max(s)
        a2 = s[-1]*w
        if r != 0:
            a2 += max(0, max(s[:r]))
        a = max(a1, a2)
    ans = max(ans, a)
print(ans)

'''

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = -float('inf')
for i in range(n):
    j = p[i] - 1
    s = [c[j]]
    while j != i:
        j = p[j] - 1
        s.append(s[-1] + c[j])
    l = len(s)
    if k <= l:
        score = max(s[:k])
    elif s[-1] <= 0:
        score = max(s)
    else:
        w, r = divmod(k, l)
        score1 = s[-1] * (w - 1)
        score1 += max(s)
        score2 = s[-1] * w
        if r != 0:
            score2 += max(0, max(s[:r]))
        score = max(score1, score2)

    ans = max(ans, score)

print(ans)
'''

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = -float('inf')
for i in range(n):
    s = []
    j = p[i]-1 
    s.append(c[j])
    while j != i:
        j = p[j]-1
        s.append(s[-1]+c[j])
    l = len(s)
    if k <= l:
        a = max(s[:k])
    elif s[-1] <= 0:
        a = max(s)
    else:
        w, r = divmod(k, l)
        a1 = s[-1]*(w-1) + max(s)
        a2 = s[-1]*w
        if r != 0:
            a2 += max(0, max(s[:r]))
        a = max(a1, a2)
    ans = max(ans, a)
print(ans)

'''

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = -float('inf')
for i in range(n):
    j = p[i] - 1
    s = [c[j]]
    while j != i:
        j = p[j] - 1
        s.append(s[-1] + c[j])
    l = len(s)
    if k <= l:
        score = max(s[:k])
    elif s[-1] <= 0:
        score = max(s)
    else:
        w, r = divmod(k, l)
        score1 = s[-1] * (w - 1)
        score1 += max(s)
        score2 = s[-1] * w
        if r != 0:
            score2 += max(0, max(s[:r]))
        score = max(score1, score2)

    ans = max(ans, score)

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

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list()
for i in range(n):
    b.append(a.count(i+1))
c = [i for i in b if i != 0]
c.sort()
if len(c) - k > 0:
    print(sum((c[0:len(c)-k])))
else:
    print(0)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [0]*n
for i in range(n):
    b[a[i]-1] += 1
c = [i for i in b if i != 0]
c.sort()
if len(c) - k > 0:
    print(sum((c[0:len(c)-k])))
else:
    print(0)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = np.zeros((N,2,N), dtype=bool) # A = {([false],[true]),,}

for i in range(N):
  for j in range(int(input())):
  	x, y = map(int,input().split())
  	A[i][y][x-1] = True

upper = 0

seed = 1 << np.arange(N)

for i in range(2**N):
  mask = (seed & i).astype(bool)
  s = np.sum(mask)
  if s <= upper: continue
  m2 = np.repeat([mask], s, axis=0).reshape(-1)
  aa = A[mask]
  a0 = aa[:,0].reshape(-1)
  if np.any(m2[a0]!=0): continue
  a1 = aa[:,1].reshape(-1)
  if np.any(m2[a1]!=1): continue
  upper = s

print(upper)

### FIXED CODE ###

import numpy as np

N = int(input())
A = np.zeros((N,2,N), dtype=bool) # A = {([false],[true]),,}

for i in range(N):
  for j in range(int(input())):
  	x, y = map(int,input().split())
  	A[i][y][x-1] = True

upper = 0

def hantei(mask):
  for a in A[mask]:
    if np.any(mask[a[0]]): return False
    if not(np.all(mask[a[1]])): return False
  return True

seed = 1 << np.arange(N)

for i in range(2**N):
  mask = (seed & i).astype(bool)
  s = np.sum(mask)
  if s <= upper: continue
  if hantei(mask): upper = s

print(upper)