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

# D
from collections import deque

# create graph
G = dict()
G_inv = dict()
N, M = map(int, input().split())
for n in range(1, N+1):
    G[n] = dict()
    G_inv[n] = dict()

for _ in range(M):
    a, b, c = map(int, input().split())
    G[a][b] = c
    G_inv[b][a] = c

# value
values = [-1000000000*2000]*(N+1)
values[1] = 0

reachable = [0]*(N+1)
reachable[N] = 1
# find reachble points
dr = deque([N])
while len(dr) > 0:
    b = dr.popleft()
    for a in G_inv[b].keys():
        if reachable[a] == 0:
            reachable[a] = 1
            dr.append(a)

# BFS
inc_cnt = 0
d = deque([1])
while len(d) > 0:
    a = d.popleft()
    for b in G[a].keys():
        if values[b] < values[a] + G[a][b]:
            values[b] = values[a] + G[a][b]
            if reachable[b] == 1:
                inc_cnt += 1
            d.append(b)
    if inc_cnt > 2000:
        break
if inc_cnt > 2000:
    print('inf')
else:
    print(values[N])

### FIXED CODE ###

# D
from collections import deque

# create graph
G = dict()
G_inv = dict()
N, M = map(int, input().split())
for n in range(1, N+1):
    G[n] = dict()
    G_inv[n] = dict()

for _ in range(M):
    a, b, c = map(int, input().split())
    G[a][b] = c
    G_inv[b][a] = c

# value
values = [-1000000000*2000]*(N+1)
values[1] = 0

reachable = [0]*(N+1)
reachable[N] = 1
# find reachble points
dr = deque([N])
while len(dr) > 0:
    b = dr.popleft()
    for a in G_inv[b].keys():
        if reachable[a] == 0:
            reachable[a] = 1
            dr.append(a)

# BFS
inc_cnt = 0
d = deque([1])
while len(d) > 0:
    a = d.popleft()
    for b in G[a].keys():
        if values[b] < values[a] + G[a][b] and reachable[b] == 1:
            values[b] = values[a] + G[a][b]
            inc_cnt += 1
            d.append(b)
    if inc_cnt > 2000:
        break
if inc_cnt > 1000:
    print('inf')
else:
    print(values[N])
### BUGGY CODE ###

N,K = map(int,input().split(' '))
S = input()
previous_idx = 0
if S[0] == 'L':
    search_s = 'R'
    non_search_s = 'L'
else:
    search_s = 'L'
    non_search_s = 'R'

flag  = False
i = 0
count_s = 0
new_S = ''
previous_s = S[0]
while K != 0 and i != N:
    if previous_s == S[i]:
        count_s +=1
        if i+1 == N:
            flag =True
            new_S += non_search_s*count_s
    else:
        if previous_s == search_s:
            new_S += non_search_s*count_s
            K -= 1
        else:
            new_S += non_search_s*count_s
        previous_s = S[i]
        count_s = 1
    i += 1
if not flag:
    new_S += S[i-1:N]
#print(new_S)
'''
while K != 0 and idx != N:
    if S[idx] == search_s:
        if not continue_flag:
            continue_flag = True
        new_S += non_search_s
    else:
        if continue_flag:
            continue_flag = False
            K -= 1
            last_idx = idx
        new_S += S[idx]
    idx += 1
new_S += S[idx:N]
#print(new_S)
'''
count_s = 0
previous_s = new_S[0]
for i in range(1,N):
    if previous_s == new_S[i]:
        count_s +=1
    else:
        previous_s = new_S[i]
print(count_s)

### FIXED CODE ###

N,K = map(int,input().split(' '))
S = input()
previous_idx = 0
if S[0] == 'L':
    search_s = 'R'
    non_search_s = 'L'
else:
    search_s = 'L'
    non_search_s = 'R'

flag  = False
i = 0
count_s = 0
new_S = ''
previous_s = S[0]
while K != 0 and i != N:
    if previous_s != S[i]:
        if previous_s == search_s:
            #new_S += non_search_s*count_s
            K -= 1
        #else:
            #new_S += non_search_s*count_s
        previous_s = S[i]
        #count_s = 1
        #count_s += 1
        #if i+1 == N:
        #    flag =True
            #new_S += non_search_s*count_s
        
    i += 1
if K > 0:
    print(N-1)
else:
    new_S += non_search_s*(i-1)
    if not flag:
        new_S += S[i-1:N]
    #print(new_S)
    count_s = 0
    previous_s = new_S[0]
    for i in range(1,N):
        if previous_s == new_S[i]:
            count_s +=1
        else:
            previous_s = new_S[i]
    print(count_s)
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(N)]
S_set = sorted(list(set(S)))

count = [0]*len(S_set)
for i in range(len(S_set)):
  count[i] = S.count(S_set[i])

#print(S_set)
for i in range(len(S_set)):
  if count[i] == max(count):
    print(S_set[i])

### FIXED CODE ###

from collections import Counter
N = int(input())
S = [input() for i in range(N)]

S_c = Counter(S)
max_count = max(S_c.values())

ans = []

for key, value in S_c.items():
  if value == max_count:
    ans.append(key)
    
ans.sort()

for i in range(len(ans)):
  print(ans[i])
### BUGGY CODE ###

N=input()
List=list(N)
p=""
ans=0
for j in range(4,len(List)+1):
  for i in range(len(List)-j+1):
    for x in range(i,i+j):
      p += List[x]
    if int(p)%2019==0:
      ans+=1
    p=""
print(ans)

### FIXED CODE ###

S = input()[::-1]

#aのMOD求めるンゴ
MOD=2019
ls_rem_a=[]
d=1
for i in range(len(S)):
  ls_rem_a.append(int(S[i])*d%MOD)
  d = d*10%MOD

#次に累積和求めるンゴ
ls_rem_s=[0]
sum=0
for i in range(len(S)):
  sum+=ls_rem_a[i]
  sum%=MOD
  ls_rem_s.append(sum)

#最後にMODが同じやつの個数を調べるンゴ
from collections import Counter
C_rem = Counter(ls_rem_s)
ans=0
for i in C_rem.keys():
  n=C_rem[i]
  ans+=n*(n-1)//2
print(ans)
### BUGGY CODE ###

def f(mtrx):
	maxSum = -10**9
	for rowStart in range(n):
		for  rowEnd in range(rowStart,n):
			for colStart in range(n):
				for colEnd in range(colStart,n):
					calcSum = 0
					for row in range(rowStart,rowEnd+1):
						calcSum += sum(mtrx[row][colStart:colEnd+1])
					maxSum = max(calcSum, maxSum)
	return maxSum
	
n = int(raw_input())
mtrx = [map(int, raw_input().split()) for i in range(n)]
print f(mtrx)

### FIXED CODE ###

def x(a):
	m=-10**9
	for c in N:
		p=[0]*n 
		for e in range(c,n):
			for r in N:
				p[r]+=a[r][e]
			m=max(P(p),m)
	return m
def P(a):
	m,c=-10**5,0
	for i in N:
		c+=a[i]
		m=max(c,m)
		if c<0:c=0
	return m
n = input()
N = range(n)
print x([map(int, raw_input().split()) for i in N])
### BUGGY CODE ###

import numpy as np
from functools import lru_cache

N, K = map(int, input().split())
A = np.array(input().split(), dtype = np.int64)

bit_cnt = [((A >> k) & 1).sum() for k in range(40)]

# @lru_cache(maxsize = 10 ** 6)

def F(K, k = 39):
    #K以下、k-bit目まで見た(inclusive)の和、最大値
    if k == -1: #最後まで見た時
        return 0
    bit = 1 << k
    #k-bitを使う
    x = 0
    if K >= bit:
        x = ((N - bit_cnt[k]) << k) + F(K - bit, k - 1)
    #k-bitを使わない
    y = (bit_cnt[k] << k) + F(min(K, bit - 1), k - 1)
    return max(x, y)

ans = F(K)
print (ans)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
ones = [0] * 40
for i in A:
    for j in range(40):
        if (i >> j) & 1:
            ones[j] += 1
x = 0
for i in range(39, -1, -1):
    if x + (1 << i) > K:
        continue
    elif ones[i] < N - ones[i]:
        x += (1 << i)

ans = 0
for i in A:
    ans += x ^ i

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

n = int(input())
for m in range(n):
    count = 0
    for i in range(n):
        x = i + 1
        xx = x * x
        if  x * x >= n:
            break
        for j in range(n):
            y = j + 1
            yy = y * y
            if xx + yy >= n:
                break
            for k in range(n):
                z = k + 1
                zz = z * z
                if xx + yy + zz + x * y + y * z + z * x > m+1:
                    break
                elif xx + yy + zz + x * y + y * z + z * x == m+1:
                    count += 1
                    break
    print(count)



### FIXED CODE ###

n = int(input())
ans = [0] * n
count = 0
for i in range(n):
    x = i + 1
    xx = x * x
    if  x * x >= n:
        break
    for j in range(n):
        y = j + 1
        yy = y * y
        if xx + yy + x * y>= n:
            break
        for k in range(n):
            z = k + 1
            zz = z * z
            kotae = xx + yy + zz + x * y + y * z + z * x
            if kotae > n:
                break
            ans[kotae-1] += 1
for i in range(n):
    print(ans[i])
### BUGGY CODE ###

from collections import Counter

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

s = input()

if 10 % p == 0:
    ans = 0
    for i, x in enumerate(s):
        if int(x) % p == 0:
            ans += i + 1
    print(ans)
else:
    li = [0]
    for i, x in enumerate(s[::-1]):
        li.append((li[-1] + int(x) * (10**i) % p) % p)

    ans = 0
    c = Counter(li[1:])
    for v in c.values():
        ans += v * (v-1)
    ans = ans // 2
    ans += c[0]
    print(ans)


### FIXED CODE ###

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

s = input()

if 10 % p == 0:
    ans = sum(i + 1 for i, x in enumerate(s) if int(x) % p == 0)
    print(ans)
else:
    counter = [0] * p
    counter[0] = 1
    cur = 0
    p10 = 1
    ans = 0
    for x in s[::-1]:
        cur = (cur + int(x) * p10) % p
        ans += counter[cur]
        counter[cur] += 1
        p10 *= 10
        p10 %= p
    print(ans)
### BUGGY CODE ###

from collections import*
import sys
input=sys.stdin.readline   #input高速化 １文字の時の改行文字に注意+

d=defaultdict(int)
db=defaultdict(int)

d[0]=0
db[0]=0

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

x=[list(map(int,input().split()))for i in range(n)]

dp=[]
dp2=[]
for time,value in x:
    for k,v in d.copy().items():
        if k+time<t:
            if d[k+time]<v+value:
                d[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        if d[i]>l[-1]:
            l.append(d[i])
        else:
            l.append(l[-1])

    dp.append(l)    
        
for time,value in x[::-1]:
    for k,v in db.copy().items():
        if k+time<t:
            if db[k+time]<v+value:
                db[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        if db[i]>l[-1]:
            l.append(db[i])
        else:
            l.append(l[-1])
        
    dp2.append(l)
dp=[[0]*t,[0]*t]+dp
dp2=([[0]*t,[0]*t]+dp2)[::-1]

ans=0

for i in range(len(dp)):
    for j in range(t):
        if i==0 or i==len(dp)-1:
            if ans<dp[i][j]+dp2[i][t-j-1]:
                ans=dp[i][j]+dp2[i][t-j-1]
        else:
            if dp[i][j]+dp2[i][t-j-1]+x[i-1][1]>ans:
                ans=dp[i][j]+dp2[i][t-j-1]+x[i-1][1]
print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline   #input高速化 １文字の時の改行文字に注意+

d={i:0 for i in range(3001)}
db={i:0 for i in range(3001)}

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

x=[tuple(map(int,input().split()))for i in n*[0]]
x.sort()
dp=[]
dp2=[]
for time,value in x:
    for k,v in d.copy().items():
        if k+time<t:
            if d[k+time]<v+value:
                d[k+time]=v+value
        else:
            break
    l=[0]
    for i in range(1,t+1):
        if d[i]>l[-1]:
            l.append(d[i])
        else:
            l.append(l[-1])

    dp.append(l)    
        
for time,value in x[::-1]:
    for k,v in db.copy().items():
        if k+time<t:
            if db[k+time]<v+value:
                db[k+time]=v+value
        else:
            break

    l=[0]
    for i in range(1,t+1):
        if db[i]>l[-1]:
            l.append(db[i])
        else:
            l.append(l[-1])
        
    dp2.append(l)
dp=[[0]*t,[0]*t]+dp
dp2=([[0]*t,[0]*t]+dp2)[::-1]

ans=0

for i in range(len(dp)):
    for j in range(t):
        if i==0 or i==len(dp)-1:
            tmp=dp[i][j]+dp2[i][t-j-1]
            if ans<tmp:
                ans=tmp
        else:
            tmp=dp[i][j]+dp2[i][t-j-1]+x[i-1][1]
            if tmp>ans:
                ans=tmp
print(ans)
### BUGGY CODE ###

from collections import Counter
import math


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


def make_divisors(n):

    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i != n and i in c:
                return False

            tmp = n // i
            if i != tmp:
                if tmp != n and tmp in c:
                    return False
    return True


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

c = Counter(A)

# 1がある時
if 1 in c:
    if c[1] >= 2:
        print(0)
    else:
        print(1)
    exit(0)

ans = 0
for a in A:
    # 同じ数が複数ある
    if c[a] >= 2:
        continue

    # 1と同数がなくて素数なら割り切れる数はない
    if is_prime(a):
        ans += 1
        continue

    # 約数があるか
    if make_divisors(a):
        ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter

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

c = Counter(A)
p = [True]*(10**6+1)

for k, v in c.items():
    t = k*2
    while t <= 10**6:
        p[t] = False
        t += k

ans = 0
for a in A:
    if c[a] == 1 and p[a]:
        ans += 1
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
DP=[1000000000]*N
DP[0]=0
for i in range(1,N):
  #j=1
  #while j<=K and j<=i:
  #  DP[i]=min(DP[i],abs(h[i]-h[i-j])+DP[i-j])
  for j in range(max(0, i-K),i):
    DP[i]=min(DP[i],abs(h[i]-h[j])+DP[j])
print(DP[-1])




### FIXED CODE ###

def main():
  #import sys
  #input = sys.stdin.readline
  N,K=map(int,input().split())
  h=list(map(int,input().split()))
  DP=[0]*N
  DP[0]=0
  for i in range(1,N):
  #j=1
  #while j<=K and j<=i:
  #  DP[i]=min(DP[i],abs(h[i]-h[i-j])+DP[i-j])
  #for j in range(max(0, i-K),i):
    #DP[i]=min(DP[i],abs(h[i]-h[j])+DP[j])
    r=max(0, i-K)
    DP[i]=min([abs(h[i]-h[j])+DP[j] for j in range(r,i)])
  print(DP[-1])
if __name__ == '__main__':
  main()
### BUGGY CODE ###

n,m = map(int,input().split())
ls = [[] for _ in range(10**5)]
k = 0
di = [list(map(int,input().split())) for _ in range(m)]
for i in range(m):
    ls[di[i][0]-1].append(di[i][1])
    if di[i][0] > k:
        k = di[i][0]
for j in range(k):
    ls[j].sort()
for l in range(m): 
    p = str(10**12 + di[l][0]*(10**6) + ls[di[l][0]-1].index(di[l][1])+1)
    print(p[1:])


### FIXED CODE ###

n,m = map(int,input().split())
ls = [[] for _ in range(n+1)]
di = []
for i in range(m):
    a,b = map(int,input().split())
    ls[a].append([b,i+1])
for j in range(n+1):
    if ls[j] != []:
        ls[j].sort(key=lambda x :x[0])
        for k in range(len(ls[j])):
            di.append([ls[j][k][1],str(10**12+j*10**6+k+1)[1:]])
di.sort(key=lambda x :x[0])
for l in range(m):
    print(di[l][1])
### BUGGY CODE ###

N = int(input())
S = input()
dp = [[0]*(N+1) for i in range(N+1)]
ans = 0
for i in range(N-1,-1,-1):
  for j in range(i,-1,-1):
    if S[i] == S[j]:
      dp[i][j] = dp[i+1][j+1] + 1
      tmp = min(dp[i][j],i-j)
      ans = max(ans,tmp)
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
dp = [[0]*(N+1) for i in range(N+1)]
ans = 0
for i in range(N-1,-1,-1):
  for j in range(i,-1,-1):
    if S[i] == S[j]:
      dp[i][j] = dp[i+1][j+1] + 1
      tmp = min(dp[i][j],i-j)
      ans = max(ans,tmp)
print(ans)
### BUGGY CODE ###

S = str(input())
N = len(S)
cnt = 0

for i in range(N):
    if N - i - 1 >= 3:
        for j in range(i+3,N):
            if int(S[i:j+1]) % 2019 == 0:
                cnt += 1
            
print(cnt)

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

n = int(input())
s = input()
x = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    for k in range(j+1, n):
      if {s[i], s[j], s[k]}=={"R", "G", "B"} and i+k != 2*j:
        x += 1
print(x)

### FIXED CODE ###

n = int(input())
s = input()
a = s.count("R")
b = s.count("G")
c = s.count("B")
z = a*b*c
R=[]
G=[]
B=[]
for i in range(n):
  if s[i]=="R":
    R.append(i)
  elif s[i]=="G":
    G.append(i)
  else:
    B.append(i)
x = 0
for i in R:
  for j in G:
    if 0 <= 2*j-i <= n-1 and s[2*j-i]=="B":
      x+=1
    if 0 <= 2*i-j <= n-1 and s[2*i-j]=="B":
      x+=1
    if (i+j)%2==0 and s[(i+j)//2]=="B":
      x+=1
print(z-x)
### BUGGY CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
MENU = [100,101,102,103,104,105]
ok = False

X = int(input())
def readInts():
  return list(map(int,input().split()))
def dfs(Price):
    global X
    global ok
    if Price >= X:
        if Price == X:
            ok = True
            return
        else:
            return
    if not ok:
        for v in MENU:
            Price += v
            if Price > X:
                Price -= v
                continue
            dfs(Price)
            Price -= v
def main():
    dfs(0)
    print(1 if ok else 0)
if __name__ == '__main__':
  main()


### FIXED CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    X = int(input())
    # O(1)解法
    quo = X//100
    mo_ = X % 100
    # 0 <= Xを100で割った余り <= 5 * Xを100で割った時の商 (最大で、5 * 商まで表せれるから)
    if 0 <= mo_ <= 5*quo:
        print(1)
    else:
        print(0)

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

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    a,b,c = readInts()
    MIN = float('inf')
    for i in range(1,c):
        MIN = min(MIN,abs(a*b*i - a*b*(c-i)))
    print(MIN)
if __name__ == '__main__':
  main()


### FIXED CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    A = sorted(readInts())
    a,b,c = A
    #MaxArea = a * b * c
    #red = 0
    #dist = MaxArea - red
    # for i in range(1,MaxArea//(a*b)//2 + 1):
    #     #print(red)
    #     red += a * b
    #     dist = min(dist,abs(MaxArea - red - red))
    #print(dist)
    print(abs(a*b*(c//2+c%2) - a*b*(c//2)))
if __name__ == '__main__':
  main()
### BUGGY CODE ###

price = [1, 5, 10, 50, 100, 500]

while True:
    values = list(map(int, input().split()))
    p, n = values[0], values[1:]
    ans = 1e100
    if p == 0:
        break

    p_sum = sum(map(lambda s: s[0] * s[1], zip(price, n)))

    for change in range(p_sum - p + 1):
        total = p + change
        pay = [0] * 6
        #for i in reversed(range(6)):
        #    if total >= price[i]:
        #        pay[i] = min(n[i], int(total / price[i]))
        #        total -= pay[i] * price[i]

        #if total > 0:
        #    break

        coins = sum(pay)

        _change = change
        for i in [5, 4, 3, 2, 1, 0]:
            if _change >= price[i]:
                coins += int(_change / price[i])
                _change %= price[i]

        ans = min(ans, coins)
    
    print(ans)

### FIXED CODE ###

price = [1, 5, 10, 50, 100, 500]

while True:
    values = list(map(int, input().split()))
    p, n = values[0], values[1:]
    ans = 1e100
    if p == 0:
        break

    p_sum = sum(map(lambda s: s[0] * s[1], zip(price, n)))

    for change in range(1000):
        total = p + change
        pay = [0] * 6
        for i in reversed(range(6)):
            if total >= price[i]:
                pay[i] = min(n[i], int(total / price[i]))
                total -= pay[i] * price[i]

        if total > 0:
            break

        coins = sum(pay)

        _change = change
        for i in reversed(range(6)):
            if _change >= price[i]:
                coins += int(_change / price[i])
                _change %= price[i]

        ans = min(ans, coins)

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

N=int(input())
A=list(map(int,input().split()))
pair=0
X2=[]

for i in range(N):
    a=A[i]
    x1=i+1-a
    x2=i+1+a
    pair+=X2.count(x1)
    X2.append(x2)
print(pair)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
pair=0
As={}

for i in range(N):
    a=A[i]
    x1=i+1-a
    x2=i+1+a
    if x1 in As:
        pair+=As[x1]
    if x2 in As:
        As[x2]+=1
    else:
      As[x2]=1
print(pair)
### BUGGY CODE ###

import numpy as np
n,w = map(int,input().split())
x = []
for i in range(n):
    x1,y1=[int(i) for i in input().split()]
    if i == 0:
      ti = x1
      zero = 0
      iti = 0
      ni = 0
      san = 0
    if x1 == ti:
      zero += 1
    elif x1 == ti+1:
      iti += 1
    elif x1 == ti+2:
      ni += 1
    else:
      san +=1
    x.append([x1,y1])
x.sort()
zer = x[:zero]
one = x[zero:iti+zero]
two = x[iti+zero:iti+ni+zero]
three = x[iti+ni+zero:zero+iti+ni+san]
zer.append([0,0])
one.append([0,0])
two.append([0,0])
three.append([0,0])
zer = sorted(zer,key = lambda x: -x[1])
one = sorted(one,key = lambda x: -x[1])
two = sorted(two,key = lambda x: -x[1])
three = sorted(three,key = lambda x: -x[1])
ans = 0
zer = np.array(zer)
one = np.array(one)
two = np.array(two)
three = np.array(three)
for i in range(len(zer)):
  for j in range(len(one)):
    for k in range(len(two)):
      for l in range(len(three)):
        omo = sum(zer[:i,0]) + sum(one[:j,0]) + sum(two[:k,0]) + sum(three[:l,0])
        kati  = sum(zer[:i,1]) + sum(one[:j,1]) + sum(two[:k,1]) + sum(three[:l,1])
        if omo <= w:
          ans = max(ans,kati)
print(ans)

### FIXED CODE ###

n,w = map(int,input().split())
x = []
for i in range(n):
    x1,y1=[int(i) for i in input().split()]
    if i == 0:
      ti = x1
      zero = 0
      iti = 0
      ni = 0
      san = 0
    if x1 == ti:
      zero += 1
    elif x1 == ti+1:
      iti += 1
    elif x1 == ti+2:
      ni += 1
    else:
      san +=1
    x.append([x1,y1])
x.sort()
zer = x[:zero]
one = x[zero:iti+zero]
two = x[iti+zero:iti+ni+zero]
three = x[iti+ni+zero:zero+iti+ni+san]
zer.append([0,0])
one.append([0,0])
two.append([0,0])
three.append([0,0])
zer = sorted(zer,key = lambda x: -x[1])
one = sorted(one,key = lambda x: -x[1])
two = sorted(two,key = lambda x: -x[1])
three = sorted(three,key = lambda x: -x[1])
ans = 0
zer0 = [0]* len(zer)+ [0]
one0 = [0]* len(one)+ [0]
two0 = [0]* len(two)+ [0]
three0 = [0]* len(three)+ [0]
zerk = [0]* len(zer)+ [0]
onek = [0]* len(one)+ [0]
twok = [0]* len(two)+ [0]
threek = [0]* len(three)+ [0]
for i in range(1,len(zer)+1):
  zer0[i] = zer0[i-1] + zer[i-1][0]
  zerk[i] = zerk[i-1] + zer[i-1][1]
for i in range(1,len(one)+1):
  one0[i] = one0[i-1] + one[i-1][0]
  onek[i] = onek[i-1] + one[i-1][1]
for i in range(1,len(two)+1):
  two0[i] = two0[i-1] + two[i-1][0]
  twok[i] = twok[i-1] + two[i-1][1]
for i in range(1,len(three)+1):
  three0[i] = three0[i-1] + three[i-1][0]
  threek[i] = threek[i-1] + three[i-1][1]
for i in range(len(zer)):
  for j in range(len(one)):
    for k in range(len(two)):
      for l in range(len(three)):
        omo = zer0[i] + one0[j] + two0[k] + three0[l]
        kati  = zerk[i] + onek[j] + twok[k] + threek[l]
        if omo <= w:
          ans = max(ans,kati)
print(ans)