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

# coding: utf-8
from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(n, k, a):
    mod = int(1e9 + 7)
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 1
    for i in range(1, n + 1):
        # csum: Cumulative sum
        # csum[j + 1] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j]
        csum = [0] + [x % mod for x in accum(dp[i - 1])]
        dpi = dp[i]
        for j in range(1, k + 1):
            l = 0 if j < a[i] else j - a[i]
            dpi[j] = csum[j + 1] - csum[l]
            if dpi[j] < 0:
                dpi[j] += mod
    return(dp[n][k])

n, k = map(int, input().split()) # 1 <= n <= 100, 0 <= k <= 10^5
a = list(map(int, input().split()))
a.insert(0, 0)
print(f(n, k, a))


### FIXED CODE ###

# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(n, k, ai):
    mod = int(1e9 + 7)
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in ai:
        # csum: Cumulative sum
        # dp[j] = dp[0] + dp[1] + ... + dp[j]
        # dp = list(accum(dp, lambda x, y: (x + y) % mod))
        dp = list(accum(dp))
        # j = 0 ～ a[i] までは累積和の結果そのままで a[i] + 1 以降は
        # dp[j] -= dp[j] - dp[j - a[i] - 1]
        dp[a + 1:] = [x - y for x, y in zip(dp[a + 1:], dp)]
        dp = [x % mod for x in dp]
    return(dp[k])

n, k = map(int, input().split()) # 1 <= n <= 100, 0 <= k <= 10^5
a = list(map(int, input().split()))
print(f(n, k, a))
### BUGGY CODE ###

n = int(input())
i = 1
divisor = (1 + n) // 2
min_value = 10 ** 10 + 1
while i <= divisor:
    if n % i == 0:
        divisor = min(n // i, divisor)
        if max(len(str(i)),len(str(n // i))) > min_value:
            break
        min_value = min(min_value,max(len(str(i)),len(str(n // i))))
    i += 1
print(min_value)


### FIXED CODE ###

n = int(input())
i = 1
divisor = n ** 0.5
min_value = 10 ** 10 + 1
while i < divisor + 1:
    if n % i == 0:
        min_value = min(min_value,max(len(str(i)),len(str(n // i))))
    i += 1
print(min_value)
### BUGGY CODE ###

n=list(map(int,input().split()))
m=list(map(int,input().split()))
maxm=sum(m)
for i in range(n[1]):
  m[m.index(max(m))]=m[m.index(max(m))]//2
 
print(sum(m))

### FIXED CODE ###

import heapq

n=list(map(int,input().split()))
m=list(map(int,input().split()))
m = [-x for x in m]
heapq.heapify(m)

for i in range(n[1]):
  x=(-1*m[0])//2
  heapq.heappop(m)
  heapq.heappush(m, -x)

ans=0
for i in range(n[0]):
  ans+=-m[i]

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

import numpy as np
words = lambda t : list(map(t, input().split()))

h,w = words(int)
wq = [0] * w

grid = []
grid.append(['#'] * (w+2))
for i in range(h):
    grid.append(['#'] + list(input()) + ['#'])
grid.append(['#'] * (w+2))

l = [[0] * (w+2) for _ in range(h+2)]
r = [[0] * (w+2) for _ in range(h+2)]
u = [[0] * (w+2) for _ in range(h+2)]
d = [[0] * (w+2) for _ in range(h+2)]

for i in range(1,h+1):
    for j in range(1,w+1):
        if grid[i][j] == '#':
            continue
        else:
            l[i][j] = l[i][j-1]+1
            u[i][j] = u[i-1][j]+1

for i in range(h+1,0,-1):
    for j in range(w+1,0,-1):
        if grid[i][j] == '#':
            continue
        else:
            r[i][j] = r[i][j+1]+1
            d[i][j] = d[i+1][j]+1

ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        ans = max(ans, l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3)

print(ans)


### FIXED CODE ###

#import numpy as np
words = lambda t : list(map(t, input().split()))



h,w = words(int)
wq = [0] * w

grid = []
for i in range(h):
    grid.append(list(input()))

ans = 0
for i in range(h):
    j = 0
    while j < w:
        #print(i,j, grid[i][j])
        if grid[i][j] == '#':
            wq[j] = 0
            j+=1
            continue
        k = 0
        while j+k < w:
            if grid[i][j+k] == '.':
                k += 1
            else:
                break
        #print(i,j,k)
        if k + h > ans:
            for x in range(j,j+k):
                vplus = 0
                if not wq[x] == 0:
                    vplus = wq[x]
                else:
                    for vi in range(i-1,-1,-1):
                        if grid[vi][x] == '#':
                            break
                        else:
                            vplus += 1
                    for vi in range(i+1,h):
                        if grid[vi][x] == '#':
                            break
                        else:
                            vplus += 1
                ans = max(ans, vplus+k)
                wq[x] = vplus
        j += k
print(ans)
### BUGGY CODE ###

N = int(input())
d = [int(i) for i in input().split()]
d.sort()
count = 0
dp = 0
for i in range(1,max(d)+1):
    dp += d.count(i)
    if dp == N / 2:
        count += 1
print(count)


### FIXED CODE ###

from collections import Counter

N = int(input())
d = [int(i) for i in input().split()]
d_dic = Counter(d)
count = 0
dp = 0
for i in range(1,max(d)+1):
    dp += d_dic[i]
    if dp == N / 2:
        count += 1
    elif dp > N / 2:
        break
print(count)
### BUGGY CODE ###

# coding: utf-8
a = int(input())
b = list(map(int,input().split()))

n = 1
m = 1

aa = a/2

if a%2 == 1:
    aa = (aa*2+1)//2

for i in range(int(aa)):
  n = n * b[i]
  
  
for i in range(int(aa),a):
    m *= b[i]
    

if n * m > 10**18:
    print('-1')
else:
    print(n*m)

### FIXED CODE ###

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

c = 0
d = 0

for i in b:
    if i == 0:
        c += 1
    elif i > 10**18:
        d += 1
        
if c > 0:
    print(0)
    exit()
if d > 1 and c == 0:
    print(-1)
    exit()

for i in b:
  n *= i
  if n > 10**18:
    print(-1)
    exit()
print(n)
### BUGGY CODE ###

def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edgesが与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  import copy
  d=copy.deepcopy(A)
  for k in range(N):
    for i in range(N):
      for j in range(N):
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  return d
 
import sys
from sys import stdin
input = stdin.readline
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
B=Warshall_Floyd(A,N)
if A!=B:
  print(-1)
  sys.exit()
 
ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j:
        if A[i][j]==A[i][k]+A[k][j]: need=0
    ans+=need*A[i][j]
print(ans)

### FIXED CODE ###

def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edges(空欄はinfとせよ)が与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k, i, j in itertools.product(range(N), range(N),range(N)):
    if edges[i][j]>edges[i][k]+edges[k][j]: return 1
  return 0
 
import sys
import itertools
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if Warshall_Floyd(A,N):
  print(-1)
  sys.exit()
 
ans=0
for i, j in itertools.product(range(N),range(N)):
  need=1
  for k in range(N):
    if k!=i and k!=j and A[i][j]==A[i][k]+A[k][j]:
      need=0
      break
  if need:ans+=A[i][j]
print(ans//2)
### BUGGY CODE ###

N, X, Y= map(int, input().split()) 
Count = []
for i in range(N-1):
  Count.append(0)
  
for k in range(1, N):
  for i in range(1, N):
    for j in range(i+1, N+1):
      if j-i <= (abs(i-X) +abs(j-Y) +1):
        if j-i == k:
          Count[k-1] = Count[k-1]+1
      else:
        if (abs(i-X) +abs(j-Y) +1) == k:
          Count[k-1] = Count[k-1]+1
for i in range(N-1):
  print(Count[i])

### FIXED CODE ###

N, X, Y= map(int, input().split()) 
Count = [0]*(N-1)
  

for i in range(1, N):
  for j in range(i+1, N+1):
    Count[min(j-i, (abs(i-X) +abs(j-Y) +1),  (abs(i-Y) +abs(j-X) +1))-1] += 1

for i in range(N-1):
  print(Count[i])
### BUGGY CODE ###




import fractions


mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def modpower(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def powerX(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 
    else            : return power(x, y//2)**2 * x

def power(x,y):
    return x ** y


def div(a, b):
    return mul(a, modpower(b, mod-2))

H,W,T = map(int,input().split())

htgcd = fractions.gcd(H,T)
wtgcd = fractions.gcd(W,T)
n = htgcd * wtgcd

p = ( 2 ** ( H // htgcd) + 2 ** (W // wtgcd) - 3)
p += 2 ** fractions.gcd( H // htgcd , W // wtgcd)

#print (p,n)

ans = modpower(p , n)

print (ans)



### FIXED CODE ###




import fractions


mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def modpower(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def powerX(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 
    else            : return power(x, y//2)**2 * x

def power(x,y):
    return x ** y


def div(a, b):
    return mul(a, modpower(b, mod-2))

H,W,T = map(int,input().split())

htgcd = fractions.gcd(H,T)
wtgcd = fractions.gcd(W,T)
n = htgcd * wtgcd

p = pow( 2, ( H // htgcd) ,mod ) +pow( 2, (W // wtgcd) , mod) - 3
p += pow(2,fractions.gcd( H // htgcd , W // wtgcd),mod)

#print (p,n)

ans = pow( p , n , mod )

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

S = input()
rem = [0]*2019

n = 0
d = 0

for s in S[::-1]:
    n = n + int(s)*10**d
    tmp = n%2019
    rem[tmp] += 1
    d += 1
    
ans = 0
for i in rem:
    ans += ((i*(i-1))//2)

print(ans+rem[0])

### FIXED CODE ###

S = input()[::-1]
rem = [0]*2019

n = 0
d = 1

for s in S:
    n = n%2019 + (int(s)*d)%2019
    tmp = n%2019
    rem[tmp] += 1
    d *= 10
    d %= 2019
    
ans = 0
for i in rem:
    ans += ((i*(i-1))//2)

print(ans+rem[0])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [list(map(int, sys.stdin.readline().split())) for _ in range(rows_number)]

def main():
    md=10**9+7
    n=int(input())
    aa=LLI(n)
    lov=[[] for _ in range(n)]
    for i,ar in enumerate(aa):
        for j,a in enumerate(ar):
            if a:lov[i].append(j)
    dp=[0]*(1<<n)
    dp[0]=1
    for s in range((1<<n)-1):
        pre=dp[s]
        if pre==0:continue
        i=bin(s).count("1")
        for j in lov[i]:
            if s>>j&1:continue
            ns=s|1<<j
            dp[ns]=(dp[ns]+pre)%md
    print(dp[-1])
    #print(dp)

main()

### FIXED CODE ###

def f(s, i):
    if i == n:
        return 1
    if memo[s] != -1:
        return memo[s]
    re = 0
    for j in range(n):
        if aij[i][j] and s & (1 << j):
            re += f(s - (1 << j), i + 1)
    re = memo[s] = re % md
    return re


md = 10 ** 9 + 7
n = int(input())
aij = [list(map(int, input().split())) for _ in range(n)]
memo = [-1] * (1 << n)
s = (1 << n) - 1
print(f(s, 0))
### BUGGY CODE ###

def main():
	N = int(input())
	seq = list(map(int, input().split()))
	seq = [seq[i] - i - 1 for i in range(N)]
	def helper(b):
		return sum([abs(seq[i] - b) for i in range(N)])
	temp = []
	for i in range(N):
		temp.append(helper(seq[i]))
	print(min(temp))
	return 0
main()

### FIXED CODE ###

def main():
	N = int(input())
	seq = list(map(int, input().split()))
	seq = [seq[i] - i - 1 for i in range(N)]
	se = sorted(list(set(seq)))
	def helper(b):
		return sum([abs(seq[i] - b) for i in range(N)])
	L = 0
	R = len(se)
	while True:
		ind = (L + R) // 2
		temp = helper(se[ind])
		if helper(se[ind - 1]) > temp and temp > helper(se[ind + 1]):
			L = ind
		elif helper(se[ind - 1]) < temp:
			R = ind
		else:
			print(temp)
			return 0
main()
### BUGGY CODE ###

n=int(input())
ass=0
for j in range(1,n+1):
  ass+=int(n/j)*(int(n/j)+1)*j//2
  
print(ass)

### FIXED CODE ###

n=int(input())
ass=0
for j in range(1,n+1):
  ass+=int(n/j)*(int(n/j)+1)*j//2
  
print(ass)
### BUGGY CODE ###

from itertools import accumulate

N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
S = [0]+list(accumulate(A))
count = 0

for i in range(N):
  num = A[i] + S[i]
  for j in range(i+1,N):
    if num*2 >= A[j]:
      num += A[j]
    else:
      count -= 1
      break
  count += 1

print(count)

### FIXED CODE ###

from itertools import accumulate

N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
S = list(accumulate(A))
AS = []
flg = False
count = 0

for i in range(N-1):
  AS.append(S[i]*2 - A[i+1])
for j in range(N-2,-1,-1):
  if AS[j] < 0:
    count = j+1
    break
print(len(A)-count)
### BUGGY CODE ###

A, B, C = map(int, input().split())
K = int(input())

while K > 0:
    if B < A:
        B *= 2
        K -= 1
    elif C < B:
        C *= 2
        K -= 1

if B > A and C > B:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

A, B, C = map(int, input().split())
K = int(input())

for i in range(K):
    if B <= A:
        B *= 2
    elif C <= B:
        C *= 2

if B > A and C > B:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

#AGC023 A
'''
問題
長さNの整数列Aがある
Nは1以上20000以下
Aiは-10**9以上10**9以下
Aの空でない連続する部分列であって，その総和が0であるものの個数は？

考察1
区間[i,j]を取り出して0になるかどうかを試す
これを0<=i<=j<=20000について繰り返す
計算時間はO(N**2)
つまりループ回数が10**10になる->大丈夫?
-> 大丈夫ではない。予想通りTLEになった

考察2
思いつかない...

解説を読んでやり直し
S0 = 0
S1 = A1
S2 = A1 + A2
...
Si = A1 + ... + Ai
とすると, 0<=p<q<=Nとなる(p,q)を選んでSq-Spを計算することによって任意の部分和を構成できる
Sq-Sp=0であればA_(p+1) + ... + Aqの部分和が0である
したがって0<=p<q<=Nとなる(p,q)に対してSp=Sqとなる(p,q)の組を数えればよい
このためにはS0,S1,...をソートして
Siをソートするところがボトルネックとなり, 計算量はO(NlogN)
'''

'''
#考察1は失敗
N = int(input())
A = list(map(int,input().split(' ')))

ans = 0

for i in range(N):
	for j in range(i,N):
		if sum(A[i:(j+1)]) == 0:
			ans += 1
		else:
			continue
			
print(ans)
'''

N = int(input())
A = list(map(int,input().split(' ')))
S = [0]
Scount = []
ans = 0

for i in range(N):
	#print(A[0:i+1])
	S.append(sum(A[0:i+1]))
	#print(S)

S = sorted(S)

for s in list(dict.fromkeys(S)):
	Scount.append(S.count(s))

for n in Scount:
	ans += (n*(n-1)/2)

print(int(ans))

### FIXED CODE ###

#AGC023 A: 部分和は先頭からの

#AGC023 A
'''
問題
長さNの整数列Aがある
Nは1以上20000以下
Aiは-10**9以上10**9以下
Aの空でない連続する部分列であって，その総和が0であるものの個数は？

考察1
区間[i,j]を取り出して0になるかどうかを試す
これを0<=i<=j<=20000について繰り返す
計算時間はO(N**2)
つまりループ回数が10**10になる->大丈夫?
-> 大丈夫ではない。予想通りTLEになった

考察2
思いつかない...

解説を読んでやり直し
S0 = 0
S1 = A1
S2 = A1 + A2
...
Si = A1 + ... + Ai
とすると, 0<=p<q<=Nとなる(p,q)を選んでSq-Spを計算することによって任意の部分和を構成できる
Sq-Sp=0であればA_(p+1) + ... + Aqの部分和が0である
したがって0<=p<q<=Nとなる(p,q)に対してSp=Sqとなる(p,q)の組を数えればよい
このためにはS0,S1,...をソートして
Siをソートするところがボトルネックとなり, 計算量はO(NlogN)
'''

'''
#考察1は失敗
N = int(input())
A = list(map(int,input().split(' ')))

ans = 0

for i in range(N):
	for j in range(i,N):
		if sum(A[i:(j+1)]) == 0:
			ans += 1
		else:
			continue
			
print(ans)
'''

N = int(input())
A = list(map(int,input().split(' ')))
S = [0]
Scount = [1]
ans = 0

for i in range(N):
	#print(A[0:i+1])
	#S.append(sum(A[0:i+1])) <- これは遅くなるのでNG
	S.append(S[-1]+A[i])
	#print(S)

S = sorted(S)

#for s in list(dict.fromkeys(S)):
	#Scount.append(S.count(s)) <- これも遅くなるのでNG
	
for i in range(N+1):
	if i==0:
		continue
	elif S[i]==S[i-1]:
		Scount[-1] += 1
	else:
		Scount.append(1)

for n in Scount:
	ans += (n*(n-1)/2)

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

import sys
sys.setrecursionlimit(10**8)
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 li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))
import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return sorted(divisors)



X = ii()
a = make_divisors(X)
for num in a:
    for i in range(num):
        j = num - i
        if i**5 + j**5 == X:
            print(i, (-1)*j)
            exit()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
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 li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

X = ii()

lim = 10**3
for a in range((-1)*lim, lim+1):
    for b in range((-1)*lim, lim+1):
        if a**5 -b**5 == X:
            print(a, b)
            exit()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)

N, Q=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(N-1)]
px=[list(map(int, input().split())) for _ in range(Q)]
to=[[] for _ in range(N)]
co=[0 for _ in range(N)]

for a, b in ab:
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)
for p, x in px:
    p-=1
    co[p]+=x

def dfs(v, p=-1):
    for u in to[v]:
        if u==p:
            continue
        co[u]+=co[v]
        dfs(u, v)

dfs(0)
print(*co)


### FIXED CODE ###

N,Q=map(int, input().split())
node_lst=[list(map(int, input().split())) for i in range(N-1)]
ope_lst=[list(map(int, input().split())) for i in range(Q)]
cnt_lst=[0 for i in range(N)]
for ope in ope_lst:
    p, x = ope[0], ope[1]
    cnt_lst[p-1]+=x
node_lst=sorted(node_lst, key=lambda x:x[0])
for l in node_lst:
    src, dst = l[0]-1, l[1]-1
    cnt_lst[dst]+=cnt_lst[src]
print(" ".join([str(c) for c in cnt_lst]))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        ans += a[i] * a[j]
ans %= 1000000007
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
a_sum = sum(a)
a_sum -= a[0]
for i in range(n - 1):
    ans += a[i] * a_sum
    a_sum -= a[i + 1]
ans %= 1000000007
print(ans)
### BUGGY CODE ###

import sys
def input():
  return sys.stdin.readline()[:-1]

def num2bi(x, k):
  return format(x, '0'+str(k)+'b')

def bi2num(b):
  return int(b, 2)

N, M=map(int, input().split())
NN=2**N

dp=[[0]+[-1]*(NN-1) for i in range(M+1)]
dp[0][0]=0
for i in range(1, M+1):
  a, b=map(int, input().split())
  c=list(map(int, input().split()))
  
  for j in range(NN):
    if dp[i-1][j]>-1:
      if dp[i][j]==-1 or dp[i][j]>dp[i-1][j]:
        dp[i][j]=dp[i-1][j]
      
      jstr=list(num2bi(j, N))
      for k in range(b):
        if jstr[c[k]-1]=='0':
          jstr[c[k]-1]='1'
          
      tmp=bi2num(''.join(jstr))
      if dp[i][tmp]==-1 or dp[i][tmp]>dp[i][j]+a:
        dp[i][tmp]=dp[i][j]+a
        
print(dp[-1][-1])

### FIXED CODE ###

#import sys
#def input():
#  return sys.stdin.readline()[:-1]

N, M=map(int, input().split())
NN=2**N

dp=[[0]+[-1]*(NN-1) for i in range(M+1)]
for i in range(1, M+1):
  a, b=map(int, input().split())
  c=list(map(int, input().split()))
  csum=sum([2**(c[s]-1) for s in range(b)])
  
  for j in range(NN):
    if dp[i-1][j]>-1:
      if dp[i][j]==-1 or dp[i][j]>dp[i-1][j]:
        dp[i][j]=dp[i-1][j]
      
      tmp=csum|j
      if dp[i][tmp]==-1 or dp[i][tmp]>dp[i][j]+a:
        dp[i][tmp]=dp[i][j]+a
        
print(dp[-1][-1])
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
import math
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

def check(t):
    res = 0
    tr = math.sqrt(abs(t))
    for ai in a:
        if ai:
            aj = t // ai
            if ai > 0:
                res += bisect_right(a, aj)
            else:
                if t % ai:
                    res += n - bisect_right(a, aj)
                else:
                    res += n - bisect_left(a, aj)
        else:
            if t >= 0:
                res += n
        if t >= 0 and abs(ai) <= tr:
            res -= 1
    return res // 2

l = - 10 ** 18
r = 10 ** 18

while r - l > 1:
    mid = (l + r) // 2
    if check(mid) < k:
        l = mid
    else:
        r = mid

if check(l) == k:
    print(l)
else:
    print(r)

### FIXED CODE ###

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

a.sort()

def check(t):
    j = n - 1 if t > 0 else 0
    res = 0
    f = 1

    cond = lambda x, t, f:x <= t if f * t > 0 or (t == 0 and f == -1) else x > t
    shift = lambda x, t:x-1 if t > 0 else x+1
    count = lambda x, n, f:n-x if f == 1 else x

    for ai in a:
        if f == 1 and ai > 0:
            f = -1
            j = n - 1 if t > 0 else 0
        if ai:
            while j >= 0 and j < n and cond(ai * a[j], t, f):
                j = shift(j, t)
            if t > 0:
                res += count(j+1, n, f)
            else:
                res += count(j, n, f)
        else:
            if t >= 0:
                res += n
        if ai * ai <= t:
            res -= 1
    return res // 2
            

m = max(max(a)**2, min(a)**2)
l = -m
r = m

while r - l > 1:
    mid = (l + r) // 2
    if check(mid) < k:
        l = mid
    else:
        r = mid

if check(l) == k:
    print(l)
else:
    print(r)
### BUGGY CODE ###

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

ans = 1
for a in al:
    ans *= a

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

### FIXED CODE ###

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

ans = 1
if al.count(0) > 0:
    print(0)
else:
    for a in al:
        ans *= a
        if ans > 10**18:
            print(-1)
            break
    else:
        print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n, max_w = map(int, input().split())

dp = [-1 for _ in range(max_w + 1)]
dp[0] = 0

for i in range(n):
    w, v = map(int, input().split())
    queue = list()
    for i in range(max_w, w - 1, -1):
        dp[i] = max(dp[i], dp[i - w] + v)

print(max(dp))

### FIXED CODE ###

# -*- coding: utf-8 -*-
n, max_w = map(int, input().split())

w = []
v = []
for i in range(n):
    _w, _v = map(int, input().split())
    w.append(_w)
    v.append(_v)

total_v = sum(v)


INF = float('inf')
dp = [[INF] * (total_v + 1) for i in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(total_v + 1):
        if j >= v[i]:
            dp[i + 1][j] = min(dp[i][j - v[i]] + w[i], dp[i + 1][j])
        dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])

for j in range(total_v, -1, -1):
    if dp[n][j] <= max_w:
        ans = j
        break

print(ans)