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

import sys
input = sys.stdin.readline

from itertools import accumulate

def main():
    N,X=map(int,input().split())
    A=[list(map(int,input().split())) for i in range(N)]

    A.sort(key=lambda x:x[2]*(X-x[0])+x[0]*x[1],reverse=True)
    ALL=[a[2]*(X-a[0])+a[0]*a[1] for a in A]



    SUM=[0]+list(accumulate(ALL))

    MAX=0
    MINUS=0

    for a,r,l in A:
        MAX+=a
        MINUS+=a*r

    OUT=-1

    def binsearch(score):

        alluse=score//X
        rest=score-alluse*X

        for ri in range(N):
            plus=0
            b,l,u=A[ri]
            
            if rest<b:
                plus+=rest*l
            else:
                plus+=rest*u+b*l-b*u

            if alluse<=ri:
                plus+=SUM[alluse]

            else:
                plus+=SUM[alluse+1]-ALL[ri]

            #print(score,ri,plus)

            if plus>=MINUS:
                return 1

        return 0


    while MAX-OUT>1:
        mid=(MAX+OUT)//2

        if binsearch(mid)==1:
            MAX=mid
        else:
            OUT=mid

    print(MAX)

main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

from itertools import accumulate

def main():
    N,X=map(int,input().split())
    A=[list(map(int,input().split())) for i in range(N)]

    A.sort(key=lambda x:x[2]*(X-x[0])+x[0]*x[1],reverse=True)
    ALL=[a[2]*(X-a[0])+a[0]*a[1] for a in A]



    SUM=[0]+list(accumulate(ALL))

    MAX=0
    MINUS=0

    for a,r,l in A:
        MAX+=a
        MINUS+=a*r

    OUT=-1

    def binsearch(score):

        alluse=score//X
        rest=score-alluse*X

        for ri in range(N):
            plus=0
            b,l,u=A[ri]
            
            if rest<b:
                plus+=rest*l
            else:
                plus+=rest*u+b*l-b*u

            if alluse<=ri:
                plus+=SUM[alluse]

            else:
                plus+=SUM[alluse+1]-ALL[ri]

            #print(score,ri,plus)

            if plus>=MINUS:
                return 1

        return 0


    while MAX-OUT>1:
        mid=(MAX+OUT)//2

        if binsearch(mid)==1:
            MAX=mid
        else:
            OUT=mid

    print(MAX)

main()
### BUGGY CODE ###

n, m = map(int, input().split())
nums = []

for i in range(n):
    nums.append(i + 1)

for i in range(m):
    l, r = map(int, input().split())
    nums = list(filter(lambda x: l <= x <= r, nums))

print(len(nums))

### FIXED CODE ###

n, m = map(int, input().split())
lr = []

for i in range(m):
    lr.append(list(map(int, input().split())))

lmax = 0
mmin = 10**5

for i in range(m):
    lmax = max(lmax, lr[i][0])
    mmin = min(mmin, lr[i][1])

print(max(0, mmin - lmax + 1))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

n = int(input())
H = list(map(int,input().split()))
dp = [0]*n

def rec(i):
    if dp[i] != 0:
        return dp[i]
    res = 0
    if i == 1 or i == 2:
        res = abs(H[i]-H[0])
        dp[i] = res
        return res
    elif i == 0:
        return 0
    else:
        res = min(abs(H[i]-H[i-2])+rec(i-2),abs(H[i]-H[i-1])+rec(i-1))
        dp[i] = res
    return res

rec(n-1)

print(dp[n-1]) 

### FIXED CODE ###

n = int(input())
H = list(map(int,input().split()))
dp = [0]*n

for i in range(1,n):
    if i == 1 or i == 2:
        dp[i] = abs(H[i]-H[0])
    else:
        dp[i] = min(abs(H[i]-H[i-2])+dp[i-2],abs(H[i]-H[i-1])+dp[i-1])

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

# 未完成
import numpy as np
N = int(input())
x = np.zeros(N)
y = np.zeros(N)
kouholist = []
ans = []
if N == 1:
    print(1)
else:
    for i in range(N):
        x[i], y[i] = map(int, input().split())
    for m in range(N):
        for p in range(N):
            if m == p:
                continue
            diff_x = x[m] - x[p]
            diff_y = y[m] - y[p]
            if (diff_x, diff_y) not in kouholist:
                kouholist.append((diff_x, diff_y))

    for list_i in kouholist:
        ans_kari = 0
        for r in range(N):
            for q in range(N):
                if x[q] - x[r] == list_i[0] and y[q] - y[r] == list_i[1]:
                    ans_kari += 1
        ans.append(ans_kari)

    print("{}".format(N-max(ans)))


### FIXED CODE ###

# 未完成

import sys
N = int(input())
x = [0]*N
y = [0]*N
kouholist = []
ans = N
if N == 1:
    print(1)
    sys.exit()

for i in range(N):
    x[i], y[i] = map(int, input().split())
for m in range(N):
    for p in range(N):
        if m == p:
            continue
        diff_x = x[m] - x[p]
        diff_y = y[m] - y[p]
        ans_kari = N
        for r in range(N):
            for q in range(N):
                if x[q] - x[r] == diff_x and y[q] - y[r] == diff_y:
                    ans_kari -= 1
        if ans_kari < ans:
            ans = ans_kari

print("{}".format(ans))
### BUGGY CODE ###

import numpy as np
from collections import deque
from heapq import *
from numba import jit

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = np.array([input() for i in range(H)])

walk_move = [[-1, 0], [0, -1], [0, 1], [1, 0]]
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i ,j])
inf = float("inf")
table = np.array([[inf for i in range(W)] for i in range(H)])
table[Ch-1, Cw-1] = 0
queue = [(Ch-1, Cw-1, 0)]

@jit
def main():
  while queue:
    x, y, cost = heappop(queue)
    for i, j in walk_move:
      dx = x+i
      dy = y+j
      if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost:
        table[dx][dy] = cost
        heappush(queue, (dx, dy, cost))
    for k, l in magic_move:
      dx = x+k
      dy = y+l
      if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost+1:
        table[dx][dy] = cost+1
        heappush(queue, (dx, dy, cost+1))
  return table[Dh-1][Dw-1]
        
ans = main()
if ans == inf:
  print("-1")
else:
  print(int(ans))

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [input() for i in range(H)]

queue = deque()
queue.append((Ch-1, Cw-1, 0))
inf = float("inf")
table = [[inf] * W for i in range(H)]
table[Ch-1][Cw-1] = 0
walk_move = ((-1, 0), (0, -1), (1, 0), (0, 1))
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i, j])

while queue:
  x, y, cost = queue.popleft()
  for i,j in walk_move:
    dx = x+i
    dy = y+j
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost:
      queue.appendleft((dx, dy, cost))
      table[dx][dy] = cost
  for k,l in magic_move:
    dx = x+k
    dy = y+l
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost+1:
      queue.append((dx, dy, cost+1))
      table[dx][dy] = cost+1

ans = table[Dh-1][Dw-1]
if ans == inf:
  print("-1")
else:
  print(table[Dh-1][Dw-1])
### BUGGY CODE ###

import numpy as np

N, K = map(int, input().split())
P = list(map(int, input().split()))
sums = []
for i in range(N - K + 1):
  sums.append(sum(P[i:i + K]))
print(((np.max(np.array(sums))) + K) / 2)


### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
E = list(map(lambda x: (int(x) + 1) / 2, input().split()))

res = np.cumsum(E)

ans = res[K - 1]
for i in range(K, N):
    if ans < res[i] - res[i - K]:
        ans = res[i] - res[i - K]
print(ans)
### BUGGY CODE ###

X,Y = map(int,input().split())

while True:
    if Y % 2 == 1:
        print('No')
        break
    elif 2*X >= Y:
        print('No')
    elif 4*X >= Y:
        print('Yes')
        break
    
    else:
        print('No')
        break

### FIXED CODE ###

X,Y = map(int,input().split())

if Y%2 != 0:
    print('No')
elif X*2 > Y:
    print('No')
elif X*4 >= Y:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

import sys

input = sys.stdin.readline

N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
    tw, tv = map(int, input().split())
    w.append(tw)
    v.append(tv)

dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

for i in range(N):
    for j in range(W + 1):
        if j - w[i] >= 0:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
        else:
            dp[i + 1][j] = dp[i][j]
print(dp[N][W])


### FIXED CODE ###

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

dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
# dp[n][w] = n番目までの品物による重量w以下の価値の総和の最大値

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(W + 1):
        if j - w >= 0:
            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 ###

N = int(input())
ans = 0
for i in range(1,N):
    ans += i
print(ans)

### FIXED CODE ###

from math import ceil
N = int(input())
n = N -1
if n == 1:
    ans = 1
elif n%2 != 0:
    ans = (1+n)*(n//2) + ceil(n/2)
else:
    ans = (1+n)*(n//2)
print(ans)
### BUGGY CODE ###

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

ans=[]

for i in p:
    ex.append((1/2*i*(i+1))/i)

for i in range(N-K+1):
    ans.append(sum(ex[i:i+K]))
    
print(max(ans))


### FIXED CODE ###

# ruisekiwa by itertools

from itertools import accumulate

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

b1=[0]+list(accumulate(p))

ans=[]

for i in range(N-K+1):
    ans.append(b1[K+i]-b1[i])
    
print((max(ans)+K)/2)
### BUGGY CODE ###

import math
from functools import reduce
import itertools
import numpy as np
  
def gcd_list(numbers):
    return reduce(math.gcd, numbers)

K=int(input())
 
l = [i for i in range(1,K+1)]
 
temp_sum=[]
for j in itertools.product(l, repeat=3):
    temp_sum.append(gcd_list(list(j)))

print(np.sum(temp_sum))

### FIXED CODE ###

import math
from functools import reduce
import itertools
import numpy as np

K = int(input())



ans = 0
for i in range(1, K + 1):
    for j in range(i, K + 1):
        for k in range(j, K + 1):
            if i == j and j == k:
                dup_num = 1
            elif i == j or j == k:
                dup_num = 3
            else:
                dup_num = 6
            ans += math.gcd(math.gcd(i, j), k) * dup_num

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

k = int(input())


arr = list(range(1,10))

x = 0
for i in range(k):
    x = arr.pop(0)
    if x % 10 != 0:
        arr.append(10*x - 1 + x%10)
    arr.append(10*x + x%10)
    if x % 10 != 9:
        arr.append(10*x + 1 + x%10)

print(x)


### FIXED CODE ###

k = int(input())

from collections import *
arr = deque(list(range(1,10)))

x = 0
for i in range(k):
    x = arr.popleft()
    if x % 10 != 0:
        arr.append(10*x - 1 + x%10)
    arr.append(10*x + x%10)
    if x % 10 != 9:
        arr.append(10*x + 1 + x%10)

print(x)
### BUGGY CODE ###

n = int(input())
a = input().split()
a.sort()
# print(a)

result = 1
for x in a:
    result *= int(x)
    if result == 0:
        break

if result > 10 ** 18:
    print(-1)
else:
    print(result)

### FIXED CODE ###

n = int(input())
a = input().split()
a.sort()
# print(a)

max_x = 10 ** 18

result = 1
for x in a:
    result *= int(x)
    if result == 0 or result > max_x:
        break

if result > max_x:
    print(-1)
else:
    print(result)
### BUGGY CODE ###

S = input()
X = S
while True:
    flg = 0
    new_S = S.replace("01","").replace("10","")
    if S == new_S:
        break
    S = new_S
print(len(X) - len(S))

### FIXED CODE ###

import sys
from collections import Counter
S = input()
ct = Counter(list(S))
if len(ct.keys()) == 1:
    print(0)
else:
    print(min(ct.values()) * 2)
### BUGGY CODE ###

import heapq
N = int(input())
a = list(map(int, input().split()))

def check(k):
    heap = []
    for i in range(k):
        heapq.heappush(heap, -1 * a[i])

    tmp = 0
    for _ in range(N):
        tmp -= heapq.heappop(heap)

    heap = []
    for i in range(k, 3 * N):
        heapq.heappush(heap, a[i])

    for _ in range(N):
        tmp -= heapq.heappop(heap)
    # print (tmp)
    return tmp

ans = -1 * 10 ** 20
for i in range(N, 2*N+1):
    ans = max(ans, check(i))
print (ans)

### FIXED CODE ###

import heapq
N = int(input())
a = list(map(int, input().split()))

heap_left = []
left = 0
for i in range(N):
    left += a[i]
    heapq.heappush(heap_left, a[i])

lst_left = [left]
for i in range(N, 2 * N):
    tmp = heapq.heappushpop(heap_left, a[i])
    left = left - tmp + a[i]
    lst_left += [left]

heap_right = []
right = 0
for i in range(2 * N, 3 * N):
    right += a[i]
    heapq.heappush(heap_right, -1 * a[i])

lst_right = [right]
for i in range(2 * N -1, N-1, -1):
    tmp = heapq.heappushpop(heap_right, -1 * a[i])
    right = right - (-1 * tmp) + a[i]
    lst_right += [right]

# print (lst_left)
# print (lst_right)
ans = -1 * 10 ** 20
for i in range(N+1):
    # print (lst_left[i], lst_right[-(i+1)])
    ans = max(ans, lst_left[i]-lst_right[-(i+1)])

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

N = int(input())
count = 0
lst = []
while N > 0:
  lst.append(N%10)
  N //= 10 
for i in lst:
  count += i
if count % 9 == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n = int(input())
result = sum(list(map(int, str(n))))
if result % 9 == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


#隣接リスト 1-index
def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def main():
    N, M = NMI()
    F = [NLI() for _ in range(M)]
    tree = make_adjlist_nond(N, F)
    
    ans = 0
    for start in range(1, N+1):
        que = deque()
        que.append(start)
        seen = [0] * (N+1)
        seen[start] = 1
        fri_cnt = 1
        while que:
            now = que.popleft()

            for goto in tree[now]:
                if seen[goto]:
                    continue
                seen[goto] = 1
                fri_cnt += 1
                que.append(goto)
        ans = max(fri_cnt, ans)
    print(ans)





if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


class UnionFind:
    def __init__(self, n):
        #親要素のノード番号を格納　xが根のとき-(サイズ)を格納
        self.par = [-1 for i in range(n)]
        self.n = n

    def find(self, x):
        #根ならその番号を返す
        if self.par[x] < 0:
            return x
        else:
            #親の親は親
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def is_same(self, x, y):
        #根が同じならTrue
        return self.find(x) == self.find(y)

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

        #木のサイズを比較し、小さいほうから大きいほうへつなぐ
        if self.par[x] > self.par[y]:
            x, y = y, x

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

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

    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.par) 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()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, M = NMI()
    F = [NLI() for _ in range(M)]
    uf = UnionFind(N)
    for a, b in F:
        a, b = a-1, b-1
        uf.unite(a, b)
    S = [uf.size(x) for x in range(N)]
    print(max(S))


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

import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix

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

matrix = [[0]*n for _ in range(n)]

for i in range(n-1):
    matrix[i][i+1] = 1
    matrix[i+1][i] = 1

matrix[x-1][y-1] = 1
matrix[y-1][x-1] = 1

matrix = np.array(matrix)
csr = csr_matrix(matrix)
result = shortest_path(csr, method='D')

for k in range(1, n):
    answer = np.sum(result==k) // 2
    print(answer)

### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix

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

v = [x-1]
u = [y-1]
for i in range(n-1):
    v.append(i)
    u.append(i+1)

csr = csr_matrix(([1]*n, (v, u)), shape=(n, n))
result = shortest_path(csr, method='D', directed=False).astype(int)
ans = np.bincount(result.ravel(), minlength=n) // 2
print(*ans[1:], sep='\n')
### BUGGY CODE ###

N,W=map(int,input().split())
wv=[[0,0]]+[list(map(int,input().split()))for _ in range(N)]
v_max=sum(wv[i][1]for i in range(N+1))

dp=[[0]*(N+1)]+[[float('inf')]*(N+1)for _ in range(v_max)]
for v in range(1,v_max+1):
    for n in range(1,N+1):
        dp[v][n]=min((dp[v][n-1],dp[v-wv[n][1]][n-1]+wv[n][0]))

print(max(v for v in range(v_max+1) if dp[v][N]<=W))

### FIXED CODE ###

N,W=map(int,input().split())
wv=[[0,0]]+[list(map(int,input().split()))for _ in range(N)]
v_max=sum(wv[i][1]for i in range(N+1))

dp=[[0]*(N+1)]+[[float('inf')]*(N+1)for _ in range(v_max)]
for v in range(1,v_max+1):
    for n in range(1,N+1):
        dp[v][n]=min((dp[v][n-1],dp[v-wv[n][1]][n-1]+wv[n][0]))

print(max(v for v in range(v_max+1) if dp[v][N]<=W))
### BUGGY CODE ###

import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	s = IS()
	t = IS()
	n = len(s)
	m = len(t)
	dp = [["" for _ in range(m+1)] for _ in range(n+1)]
	for i in range(n):
		for j in range(m):
			if(s[i]==t[j]):
				c = [dp[i+1][j],dp[i][j+1],dp[i][j]+s[i]]
				p = np.argmax(list(map(len, c)))
				dp[i+1][j+1] = c[p]
			else:
				c = [dp[i+1][j],dp[i][j+1]]
				p = np.argmax(list(map(len, c)))
				dp[i+1][j+1] = c[p]
	print(dp[n][m])

if __name__ == '__main__':
	main()

### FIXED CODE ###

s = input()
n = len(s)
t = input()
m = len(t)

dp = [[0 for _ in range(m+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(m):
        if t[j]!=s[i]:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
        else :
            dp[i+1][j+1]=dp[i][j]+1

ans = ''

i = len(s)
j = len(t)
while (i>0  and j>0):
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans += s[i-1]
        i -= 1
        j -= 1

print(ans[::-1])
### BUGGY CODE ###

N,M=map(int,input().split())
A=[int(input()) for i in range(M)]
if 1 in A:
    B=[1]+[0]*N
else:
    B=[1]+[1]+[0]*(N-1)
for i in range(2,N+1):
    if i not in A:
        B[i]=(B[i-1]+B[i-2])%(10**9+7)
print(B[-1])

### FIXED CODE ###

N,M=map(int,input().split())
B=[1]+[1]+[0]*(N-1)
for j in range(M):
    a=int(input())
    B[a]=-1
    if a==1:
        B[a]=0
i=2
while i<=N:
    if B[i]==-1:
        B[i]=0
    else:
        B[i] = (B[i - 1] + B[i - 2]) % (10 ** 9 + 7)
    i+=1
print(B[N])
### BUGGY CODE ###

from collections import defaultdict, deque

n, m = [int(i) for i in input().split()]

children = defaultdict(list)
parents = defaultdict(list)

for _ in range(m):
    u, v = [int(i) for i in input().split()]
    children[u-1].append(v-1)
    parents[v-1].append(u-1)

def longest_path(children, parents, n):
    f = [None] * n
    targets = [x for y in children.values() for x in y]
    starts = [v for v in range(n) if v not in targets]

    for v in starts:
        f[v] = 0

    # print f
    for i in range(n):
        get_f(children, parents, f, i)

    # print f
    return max(f)

def get_f(children, parents, f, i):
    if f[i] != None:
        return f[i]

    f[i] = 0
    for v in parents[i]:
        f[i] = max(f[i], get_f(children, parents, f, v) + 1)

    return f[i]

# def longest_path(children, parents, n):
#     targets = [x for y in children.values() for x in y]
#     starts = [v for v in range(n) if v not in targets]
#     f = [None] * n
    
#     Q = deque([])
#     for v in starts:
#         f[v] = 0
#         Q.append((v, 0))

#     output = 0
#     while len(Q) > 0:
#         node, length = Q.pop()
#         output = max(output, length)
#         for v in children[node]:
#             Q.append((v, length+1))

#     return output

print(longest_path(children, parents, n))


### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)

n, m = [int(i) for i in raw_input().split()]
parents = defaultdict(list)

i = 0
while i < m:
    u, v = [int(x) for x in raw_input().split()]
    parents[v-1].append(u-1)
    i += 1

def calc_f(parents, f, i):
    if i < 0 or i >= len(f):
        return 0

    if f[i] != -1:
        return f[i]

    f[i] = 0
    for v in parents[i]:
        f[i] = max(f[i], calc_f(parents, f, v)+1)

    return f[i]

f = [-1] * n
j = 0
while j < n:
    calc_f(parents, f, j)
    j += 1

if len(f) == 0:
    print 0
else:
    print max(f)
### BUGGY CODE ###

from collections import Counter
s = input()

si = [0] * (len(s)+1) #mod2019の累積和用に
tmp = 0
for i in range(1,len(s)+1): #累積和の作成
    tmp += int(s[-i]) * 10**(i-1) % 2019
    si[i] = tmp % 2019

c = Counter(si)
ans = 0
for a,b in c.items():#aがb回出てきたよ
    ans += b*(b-1)//2

print(ans)


### FIXED CODE ###

from collections import Counter
s = str(input())

si = [0] * (len(s)+1) #mod2019の累積和用に
tmp = 0
for i in range(1,len(s)+1): #累積和の作成
    tmp += int(s[len(s)-i])%2019 * pow(10,i-1,2019)
    si[i] = tmp % 2019

c = Counter(si)
ans = 0
for b in list(c.values()):#aがb回出てきたよ
    ans += b*(b-1)//2

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

r1, c1, r2, c2 = list(map(int, input().split()))
MOD = 10 ** 9 + 7

r = (r2 + 1)
l = (r1)
ans = 0

for i in range(0, c2):
    r *= (r2 + 1 + (i + 1))
    r *= pow((i + 2), MOD - 2, MOD)
    l *= (r1 + (i + 1))
    l *= pow((i + 2), MOD - 2, MOD)
    r %= MOD
    l %= MOD
    if i >= c1 - 1:
        ans += r
        ans -= l
    ans %= MOD
print(ans % MOD)

### FIXED CODE ###

r1, c1, r2, c2 = list(map(int, input().split()))
MOD = 10 ** 9 + 7

r = (r2 + 1)
l = (r1)
ans = 0

for i in range(0, c2):
    gyaku = pow((i + 2), MOD - 2, MOD)
    r *= (r2 + 1 + (i + 1))
    r *= gyaku
    l *= (r1 + (i + 1))
    l *= gyaku
    r %= MOD
    l %= MOD
    if i >= c1 - 1:
        ans += r
        ans -= l
    ans %= MOD
print(ans % MOD)