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

n,m = map(int,input().split())
dp = []
key = []
for i in range(m):
    d = [float('inf')]*(2**n)
    d[0] = 0
    dp.append(d)
for i in range(m):
    cost,num = map(int,input().split())
    if num == 1:
        t = int(input())
        key.append([cost,2**(t-1)])
    else:
        p = list(map(int,input().split()))
        cur = 0
        for i in range(len(p)):
            cur += 2**(p[i]-1)
        key.append([cost,cur])
for i in range(m):
    for j in range(2**n):
        if i != 0:
            dp[i][j] = min(dp[i][j],dp[i-1][j])
        dp[i][j|key[i][1]] = min(dp[i][j|key[i][1]],dp[i][j]+key[i][0])
if dp[m-1][2**n-1] != float('inf'):
    print(dp[m-1][2**n-1])
else:
    print(-1)


### FIXED CODE ###

n,m = map(int,input().split())
dp = []
key = []
for i in range(m):
    d = [10**15]*(2**n)
    d[0] = 0
    dp.append(d)
for i in range(m):
    cost,num = map(int,input().split())
    if num == 1:
        t = int(input())
        key.append([cost,2**(t-1)])
    else:
        p = list(map(int,input().split()))
        cur = 0
        for i in range(len(p)):
            cur += 2**(p[i]-1)
        key.append([cost,cur])
for i in range(m):
    for j in range(2**n):
        if i != 0:
            dp[i][j] = min(dp[i][j],dp[i-1][j])
        dp[i][j|key[i][1]] = min(dp[i][j|key[i][1]],dp[i][j]+key[i][0])
if dp[m-1][2**n-1] != 10**15:
    print(dp[m-1][2**n-1])
else:
    print(-1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
j = 1
for i in A:
    j = i * j
if j > 10**18:
    print(-1)
else:
    print(j)

### FIXED CODE ###

N = int(input())
A = sorted(list(map(int, input().split())), )
j = 1
if A[0] == 0:
    print(0)
    exit()
for i in A:
    j = i * j
    if j > 10**18:
        print(-1)
        exit()
if j > 10**18:
    print(-1)
else:
    print(j)
### BUGGY CODE ###

def merge(a, left, mid, right):
    INF = int(1e+11)
    n1 = mid - left
    n2 = right - mid

    l = []
    for i in range(n1):
        l.append(a[left + i])
    r = []
    for i in range(n2):
        r.append(a[mid + i])
    l.append(INF)
    r.append(INF)
    i = 0
    j = 0

    ans = 0

    for k in range(left, right):
        ans += 1
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1
    
    return ans


def merge_sort(a, left, right):
    ans = 0
    if left + 1 < right:
        mid = (left + right) // 2
        ans += merge_sort(a, left, mid)
        ans += merge_sort(a, mid, right)
        ans += merge(a, left, mid, right)
    return ans


def print_list_split_whitespace(s):
    for x in s[:-1]:
        print(x, end=" ")
    print(s[-1])

n = int(input())
s = [int(x) for x in input().split()]

ans = merge_sort(s, 0, len(s))

print_list_split_whitespace(s)
print(ans)


### FIXED CODE ###

def merge(a, left, mid, right):
    INF = int(1e+11)
    l = a[left:mid]
    r = a[mid:right]
    l.append(INF)
    r.append(INF)
    i = 0
    j = 0

    ans = 0

    for k in range(left, right):
        ans += 1
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1
    
    return ans


def merge_sort(a, left, right):
    ans = 0
    if left + 1 < right:
        mid = (left + right) // 2
        ans += merge_sort(a, left, mid)
        ans += merge_sort(a, mid, right)
        ans += merge(a, left, mid, right)
    return ans


def print_list_split_whitespace(s):
    for x in s[:-1]:
        print(x, end=" ")
    print(s[-1])

n = int(input())
s = [int(x) for x in input().split()]

ans = merge_sort(s, 0, len(s))

print_list_split_whitespace(s)
print(ans)
### BUGGY CODE ###

import re
import numpy as np

H,W,K = map(int,input().split())
grid = []
for i in range(H):
  S = input()
  grid.append( [S[i] for i in range(W) ])
grid = np.array(grid,dtype='int64')

min_cnt = 1000*10+1
#横の区切りを作る
for j in range(2**(H-1)):
  cnt = 0
  #二進数の文字列を取得
  bin_str = format(j,"0{}b".format(H-1)) 
  #区切りのインデックスリスト
  l_p =[0]+[ x.start()+1 for x in re.finditer("1",bin_str) ] +[H]

  #cntに区切りの分だけ付け加える
  cnt = cnt + len(l_p)-2
  
  #決めた行の区切りに対して、列ごとの和の配列を取得
  L = np.empty((0,W),int)
  for i in range(len(l_p)-1):
    slice_wa = [np.sum(grid[l_p[i]:l_p[i+1],:],axis=0)]
    L = np.append(L, slice_wa ,axis=0)

  tate = np.zeros( len(l_p)-1 ,dtype='int64')
  for w in range(W):#k以上の要素があるか
    n_tate = tate + L[:,w]
    if True in (n_tate > K):
      cnt = cnt + 1
      tate = np.zeros( len(l_p)-1 ,dtype='int64')+L[:,w]   
    else:
      tate = n_tate
  min_cnt = min(cnt,min_cnt)   
###
print(min_cnt)

### FIXED CODE ###

import re

H,W,K = map(int,input().split())
grid = [[0 for i in range(W+1)]]
for i in range(H):
  S = input()
  grid.append([0]+[ int(S[i]) for i in range(W) ])

#累積和gridの作成
#行について
for i in range(H+1):
  for j in range(W):
    grid[i][j+1] += grid[i][j]
#列について
for j in range(W+1):
  for i in range(H):
    grid[i+1][j] += grid[i][j]   

min_cnt = (H-1)*(W-1)
#横の区切りを作る
for h in range(2**(H-1)):
  cnt = 0
  #二進数の文字列を取得
  bin_str = format(h,"0{}b".format(H-1)) 
  #区切りのインデックスリスト
  l_p =[1]+[ x.start()+2 for x in re.finditer("1",bin_str) ] +[H+1]

  #cntに区切りの分だけ付け加える
  cnt = cnt + len(l_p) - 2
  
  ws = 0
  for w in range(1,W+1):
    for k in range(len(l_p)-1):
      if grid[l_p[k+1]-1][w]-grid[l_p[k+1]-1][w-1] > K:
        min_cnt=(H-1)*(W-1)+1
      if grid[l_p[k+1]-1][w]- (grid[l_p[k]-1][w]+grid[l_p[k+1]-1][ws]-grid[l_p[k]-1][ws]) > K:
        cnt = cnt + 1
        ws = w-1
        break    
  min_cnt = min(min_cnt,cnt)

###
print(min_cnt)
### BUGGY CODE ###

from collections import Counter

N = int(input())
A = list(map(int,input().split()))
X = Counter(A)
for i in range(1,N+1):
    if i in A:
        print(X[i])
    else:
        print(0)


### FIXED CODE ###

N = int(input())
X = [0]*N
A = list(map(int,input().split()))
for i in A:
    X[i-1] +=1
print(*X,sep="\n")
### BUGGY CODE ###

def sol(l,o):
    t=len(bin(o))

    for i in range(o,0,-1):
        x=bin(i)
        if len(x)<t: break
        for a,b in enumerate(x[::-1]):
            if b=="b": break
            if b=="1": l[a]=(l[a]+1)%2
    return l


l=[0]*42
n,k=map(int,input().split())
#"ans=n
ans=0
l=sol(l,n-1)
l=sol(l,k)
p=1
for i in l:
    ans+=i*p
    p*=2
print(ans)


### FIXED CODE ###

p=[0]*42
q=[0]*42
x=1
a,b=map(int,input().split())
if a==b:
    print(a)
    exit()

a-=1
for i in range(42):
    if b//x<1: break
    if x==1:
        q[0]=((b+1)//2)%2
    else:
        q[i]=[0,((b+1)%x)%2][(b//x)%2]
    x*=2
x=1
for i in range(42):
    if a//x<1: break
    if x==1:
        p[0]=((a+1)//2)%2
    else:
        p[i]=[0,((a+1)%x)%2][(a//x)%2]
    x*=2
x=1
ans=0
for i in range(42):
    ans+=(p[i]^q[i])*x
    x*=2
print(ans)
### BUGGY CODE ###

n=int(input())
s = [input() for _ in range(n)]
t=[]
for i in s:
  if not i in t:
    t.append(i)
print(len(t))

### FIXED CODE ###

n=int(input())
s = [input() for _ in range(n)]
print(len(set(s)))
### BUGGY CODE ###

inputs = open(0).readlines()
n = int(inputs[0])
S = inputs[1].strip()

def is_cond(i, j, k):
    return j-i != k-j

l = []
for i in range(n-2):
    rest = {'R', 'G', 'B'}
    rest.remove(S[i])
    for j in range(i+1, n-1):
        if S[j] in rest:
            rest.remove(S[j])
            for k in range(j+1, n):
                if S[k] in rest:
                    if is_cond(i, j, k):
                        l.append((i, j, k))
            rest.add(S[j])
print(len(l))

### FIXED CODE ###

n = int(input())
S = input().strip()
r, g, b = map(S.count, 'RGB')
t = 0
for i in range(n-2):
    for w in range(1, (n-i+1) // 2):
        t += len({S[i], S[i+w], S[i+2*w]}) == 3
print(r*g*b - t)
### 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):
    x=l[i]
    dp[i]=min([(dp[j]+abs(x-l[j])) for j in range(max(0,i-k),i)])
print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int, input().split()))
v=[0]*n
for i in range(1,n):
	u = h[i]
	v[i] = min([v[j] + abs(h[j]-u) for j in range(max(0, i-k), i)])
print(v[n-1])
### BUGGY CODE ###

n,*a=map(int,open(0).read().split())
ans=1
for i in range(n):
  ans*=a[i]
if ans>10**18:
  ans=-1
print(ans)

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
ans=1
if 0 in a:
  ans=0
else:
  for i in range(n):
    ans*=a[i]
    if ans>10**18:
      ans=-1
      break
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]

o = '\n'.join([str(A.count(i)) for i in range(1, N+1)])
print(o)


### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]
x = [0] * N

for i in A:
    x[i-1] += 1

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

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
li=[]

for i in range(m):
    if ab[i][0]==1:
        li.append(ab[i][1])

li=list(set(li))

for j in range(m):
    if ab[j][0] in li:
        if ab[j][1]==n:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

### FIXED CODE ###

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

sa=set()
sb=set()

for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        sb.add(b)
    if b==n:
        sa.add(a)

if sa&sb:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

N = int(input())
X = str(input())
X10 = int(X,2)

one_num = X.count("1")

for i in range(N):
    target = int(X[i])
    if target == 0:
        ones = one_num + 1
        plus = pow(2,N-i-1)
        
    else:
        ones = one_num-1
        plus = -pow(2,N-i-1)
        
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        
        while Xnow > 0:
            Xnow2 = bin(Xnow)
            ones = Xnow2.count("1")
            Xnow = Xnow%ones
            count+=1
            
        print(count)



### FIXED CODE ###

N = int(input())
x2 = input()
x10 = int(x2, 2)
popc =  x2.count("1")
#print("x10", x10)
#print("popc", popc)
#popc: Nを2進数で表したときの1の個数

#以下で1つフリップさせた時の入力に対する余りを事前に計算
if popc <= 1:
    xp = x10%(popc+1)
    xm = 0
else:
    xp = x10%(popc+1)
    xm = x10%(popc-1)
#print("xp", xp)
#print("xm", xm)

#以下でフリップさせた場所のみを計算
for i in range(N):
    if x2[i] == "1":
        if popc == 1:
            print(0)
            continue
        tmp = (xm - pow(2, N-i-1, popc-1))%(popc-1)
    else:
        tmp = (xp + pow(2, N-i-1, popc+1))%(popc+1)
        
    #print("tmp", tmp)
    ans = 1
    while tmp > 0:
        tmp %= bin(tmp).count("1")
        ans += 1
    print(ans)
### BUGGY CODE ###

N = int(input())
P = []
for i in range(N):
    s = int(input())
    if not s in P:
        P.append(s)
    else:
        P.remove(s)
print(len(P))

### FIXED CODE ###

s = set()
N = int(input())
for _ in range(N):
    x = int(input())
    if x in s:
        s.remove(x)
    else:
        s.add(x)
print(len(s))
### BUGGY CODE ###

#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N = int(input())
A = [int(input()) for _ in range(N)]
pos = copy.deepcopy(A)
ans = 0
while len(pos) > 0:
    LIS = deque([])
    for i in range(len(pos)):
        temp = bisect.bisect_left(LIS, pos[i])
        if len(LIS) <= temp:
            LIS.append(pos[i])
        else:
            LIS[temp] = pos[i]
    ans += 1
    pos2 = []
    for i in range(len(pos)):
        if len(LIS) != 0:
            if pos[i] == LIS[0]:
                LIS.popleft()
            else:
                pos2.append(pos[i])
        else:
            pos2.append(pos[i])
    pos = pos2
print(ans)

### FIXED CODE ###

#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N = int(input())
A = [int(input()) for _ in range(N)]
Min = [A[-1]]
for i in range(N - 2, -1, -1):
    temp = bisect.bisect_right(Min, A[i])
    if temp == len(Min):
        Min.append(A[i])
    elif Min[temp] != A[i]:
        Min[temp] = A[i]
    elif temp + 1 != len(Min):
        Min[temp + 1] = A[i]
    else:
        Min.append(A[i])
print(len(Min))
### BUGGY CODE ###

import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()
ans = 0
for a in A:
    i = bisect.bisect_right(B, a)
    for b in B[i:]:
        j = bisect.bisect_right(C, b)
        ans += N-j
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()
ans = 0
for b in B:
    i = bisect.bisect_left(A, b)
    j = bisect.bisect_right(C, b)
    ans += i*(N-j)
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

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

for i in range(N-1, -1, -1):
    for j in range(N-1, -1, -1):
        if S[i] != S[j]:
            dp[i][j] = 0
        else:         
            dp[i][j] = dp[i+1][j+1] + 1
ans = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        ans = max(ans, min(dp[i][j], j-i))

print(ans)

### FIXED CODE ###

N = int(input())
S = input()

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

for i in range(N-1, -1, -1):
    for j in range(N-1, -1, -1):
        if S[i] != S[j]:
            dp[i][j] = 0
        else:         
            dp[i][j] = dp[i+1][j+1] + 1
ans = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        ans = max(ans, min(dp[i][j], j-i))

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

from fractions import gcd

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

agcd=gcd(a[0],a[1])
alcm=a[0]*a[1]//agcd
for i in range(n-2):
    agcd=gcd(alcm,a[i+2])
    alcm=alcm*a[i+2]//agcd
    
#print(alcm)
    
if 1==1:
    fmax=0
    for i in range(alcm):
        f=0
        for j in range(n):
            f=f+(i%a[j])
        if f>fmax:
            fmax=f
    print(fmax)

### FIXED CODE ###

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

s=0
for i in range(n):
    s=s+a[i]-1
    
print(s)
### BUGGY CODE ###

import collections
N=int(input())
A=list(map(int, input().split()))
A_dict=collections.Counter(A)
ANS=1

for i in A_dict.keys():
    ANS=ANS*(i**A_dict[i])

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

### FIXED CODE ###

import collections
import sys

N=int(input())
A=list(map(int, input().split()))
A_dict=collections.Counter(A)
ANS=1
if 0 in A_dict.keys():
    print("0")
    sys.exit()
    
for key, value in A_dict.items():
    ANS=ANS*(key**value)
    if ANS>10**18:
        print(-1)
        sys.exit()

print(ANS)
### BUGGY CODE ###

if __name__ == '__main__':
    n, k = list(map(int, input().split(" ")))
    p = list(map(int, input().split(" ")))

    max_sum = 0
    for i in range(n - k + 1):
        # print(i, p, k)
        r = sum(p[i:i + k])
        # print(r)
        if r > max_sum:
            max_sum = r

    print((max_sum / 2) + (k * 0.5))

### FIXED CODE ###

from collections import deque

if __name__ == '__main__':
    n, k = list(map(int, input().split(" ")))
    p = list(map(int, input().split(" ")))

    d = deque([0])
    for i in range(n):
        d.append(d[i] + p[i])

    # print(d)

    max_sum = 0
    rangeN = n - k + 1

    for i in range(rangeN):
        max_sum = max(max_sum, d[i + k] - d[i])
    # print(max_sum)

    # r_array = [sum(p[i:i + k]) for i in range(rangeN)]
    print((max_sum / 2) + (k * 0.5))
### BUGGY CODE ###

N = int(input())

e = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
c = list(map(int,input().split()))
c.sort()
c.reverse()
ans = sum(c)-c[0]
d = [0]*N
k = 0
d[0] = str(c[k])
k += 1
for _ in range(N-1):
    for i in range(N-1):
        a,b = e[i]
        if d[a]==0 and d[b]!=0:
            d[a] = str(c[k])
            k+=1
        elif d[a]!=0 and d[b]==0:
            d[b] = str(c[k])
            k+=1
print(ans)
print(' '.join(d))

### FIXED CODE ###

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

N = int(input())

e = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append((1,b))
    e[b].append((1,a))

c = list(map(int,input().split()))
c.sort()
print(sum(c)-c[-1])
d = dijkstra(e,N,0)
d = [(d[i],i) for i in range(N)]
d.sort()
d = [(d[i][0],d[i][1],c[-i-1]) for i in range(N)]
d.sort(key=lambda x:x[1])
ans = [str(d[i][2]) for i in range(N)]
print(' '.join(ans))
### BUGGY CODE ###

n=int(input())
p=list(map(int,input().split()))
m=0
d=[]
t=[]
for i in range(n):
    if p[i]==i+1:
        d.append(i)
for i in range(1,len(d)):
    if d[i]==1+d[i-1] and i-1 not in t:
        t.append(i)
        t.append(i-1)
print(len(d)-len(t)//2)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
m=0
d=[0]*n
t=set()
for i in range(n):
    if p[i]==i+1:
        d[i]=i+1
        m+=1
    if i!=0 and d[i]==1+d[i-1] and i-1 not in t:
        t.add(i)
print(m-len(t))
### BUGGY CODE ###

n,m,l = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
    a,b,c = map(int, input().split())
    a,b = a-1,b-1
    if c <= l:
        G[a].append((b,c))
        G[b].append((a,c))

from collections import deque

def check(s,t):
    DP1 = [-1]*n
    DP2 = [float("inf")]*n
    
    q = deque()
    q.append((s,0,l))
    while q:
        cur, cnt, rem = q.popleft()
        if DP2[cur] < cnt:
            continue
        if DP2[cur] == cnt and DP1[cur] > rem:
            continue
        DP2[cur] = cnt
        DP1[cur] = rem
        for to, c in G[cur]:
            if rem >= c:
                if DP2[to] > cnt or (DP2[to] == cnt and DP1[to]<rem-c):
                    q.appendleft((to,cnt,rem-c))
            if DP2[to] > cnt+1:
                q.append((to,cnt+1,l-c))
    ret = DP2[t]
    if ret == float("inf"):
        ret = -1
    return ret



q = int(input())
ans = []
for i in range(q):
    s,t = map(int, input().split())
    s,t = s-1, t-1
    ans.append(check(s,t))
print(*ans, sep="\n")

### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
import sys
input = sys.stdin.readline

def main():
    INF = float("Inf")
    n,m,l = map(int, input().split())
    G = [[INF]*n for i in range(n)]
    for i in range(n):
        G[i][i] = 0
    for i in range(m):
        a,b,c = map(int, input().split())
        a,b = a-1,b-1
        if c <= l:
            G[a][b] = G[b][a] = c
    G = floyd_warshall(G, directed=False)
    G = np.where(G <=l, 1, INF)
    for i in range(n):
        G[i][i] = 0
    GG = floyd_warshall(G, directed=False)

    q = int(input())
    ans = []
    for i in range(q):
        s,t = map(int, input().split())
        a = GG[s-1][t-1]
        if a == INF:
            a = 0
        else:
            a = int(a)
        ans.append(a-1)
    print(*ans, sep="\n")

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

n,q=map(int,input().split())
s=input()
for i in range(q):
    l,r=map(int,input().split())
    ss = s[l-1:r]
    print(ss.count('AC'))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()

ac_count=[]
ac=0

for i in range(n-1):
    if s[i:i+2]=='AC':
        ac+=1
    ac_count.append(ac)
    
for i in range(q):
    l,r=map(int,input().split())
    if l==1:
        print(ac_count[r-2])
    else:
        print(ac_count[r-2]-ac_count[l-2])
### BUGGY CODE ###

import bisect

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

count=0
L=sorted(L)
for i in range(0,N-1):
  for j in range(i+1,N):
    index=bisect.bisect_left(L[j+1:],L[i]+L[j])
    count+=index
print(count)

### FIXED CODE ###

import bisect
 
N=int(input())
L=list(map(int,input().split()))
 
L.sort()
count=0
for i in range(N):
  for j in range(i+1,N):
    c=L[i]+L[j]
    index=bisect.bisect_left(L,c)
    count+=max(0,index-j-1)
print(count)
### BUGGY CODE ###

inp = input().split()
n, k = int(inp[0]), int(inp[1])
p = input().split()
p = list(map(int, p))
max_ = 0
for i in range(n-k+1):
  sum_ = 0
  for j in range(k):
    temp = p[i+j]
    sum_ = sum_ + (temp+1)/2
  if sum_ > max_:
    max_ = sum_
print(max_)

### FIXED CODE ###

inp = input().split()
n, k = int(inp[0]), int(inp[1])
p = input().split()
p = list(map(int, p))
sum_ = 0
max_ = 0
for i in range(n):
    sum_ += p[i]
    if i >= k:
        sum_ -= p[i-k]
    if sum_ > max_:
        max_ = sum_
print((max_+k)/2)
### BUGGY CODE ###

# coding: utf-8
n,m=map(int,input().split())
edge=[]
for i in range(m):
    a,b,c=map(int,input().split())
    edge.append((a-1,b-1,-c))
inf=99999999999999999999
d=[inf for i in range(n)]
d[0]=0
count=0
while True:
    count+=1
    if count==n:
        tmp=d[n-1]
    update=False
    for i in range(m):
        f,t,cost=edge[i]
        if(d[t]>d[f]+cost):
            d[t]=d[f]+cost
            update=True
    if count==n and tmp!=d[n-1]:
        print('inf')
        break
    if not update:
        print(-d[n-1])
        break

### FIXED CODE ###

# coding: utf-8
n,m=map(int,input().split())
edge=[]
for i in range(m):
    a,b,c=map(int,input().split())
    edge.append((a-1,b-1,-c))
inf=99999999999999999999
d=[inf for i in range(n)]
d[0]=0
count=0
while count<n+1:
    count+=1
    if count==n:
        tmp=d[n-1]
    update=False
    for i in range(m):
        f,t,cost=edge[i]
        if(d[t]>d[f]+cost):
            d[t]=d[f]+cost
            update=True
    if count==n and tmp!=d[n-1]:
        print('inf')
        break
    if not update:
        print(-d[n-1])
        break
else:
    print(-d[n-1])