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

# coding: utf-8
# Your code here!
N=int(input())
A=list(map(int,input().split()))
l=[0]*N

for i in range(N):
    l[i]=l[i-1]+A[i]


ans=l.count(0)
for i in range(N):
    for j in range(i):
        if l[i]==l[j]:
            ans+=1

print(ans)



### FIXED CODE ###

# coding: utf-8
# Your code here!
import collections

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

l=[0]
for i in range(N):
    temp=l[-1]+A[i]
    l.append(temp)

c=collections.Counter(l)
#print(l)
#print(c)

_, count=zip(*c.most_common())

ans=0
for item in count:
    ans+=item*(item-1)//2
    
print(ans)
#for item in l:
### BUGGY CODE ###

import numpy as np
def solve(n, x, y):
    def dist(i, j):
        return min(abs(x[i]-x[j]), abs(y[i]-y[j]))
    que = []
    for p in map(np.argsort, [x, y]):
        for i in range(n-1):
            u, v = p[i], p[i+1]
            que.append((u, v, dist(u, v)))
    parent = {i: i for i in range(n)}
    def find(i):
        if parent[i] == i:
            return i
        else:
            j = find(parent[i])
            parent[i] = j
            return j
    ans = 0
    for u, v, d in sorted(que, key=lambda _: _[2]):
        u = find(u)
        v = find(v)
        if u != v:
            ans += d
            if u > v:
                u, v = v, u
            parent[v] = u
    return ans

n = int(input())
x = np.zeros(n, dtype=int)
y = np.zeros(n, dtype=int)
for i in range(n):
    x[i], y[i] = map(int, input().split())
print(solve(n, x, y))


### FIXED CODE ###

import numpy as np

def solve(n, x, y):
    def dist(i, j):
        return min(abs(x[i]-x[j]), abs(y[i]-y[j]))
    que = []
    for p in map(np.argsort, [x, y]):
        for i in range(n-1):
            u, v = p[i], p[i+1]
            que.append((u, v, dist(u, v)))
    parent = [i for i in range(n)]
    def find(i):
        if parent[i] == i:
            return i
        else:
            j = find(parent[i])
            parent[i] = j
            return j
    ans = 0
    for u, v, d in sorted(que, key=lambda _: _[2]):
        u = find(u)
        v = find(v)
        if u != v:
            ans += d
            if u > v:
                u, v = v, u
            parent[v] = u
    return ans

n = int(input())
x = np.zeros(n, dtype=int)
y = np.zeros(n, dtype=int)
for i in range(n):
    x[i], y[i] = map(int, input().split())
print(solve(n, x, y))
### BUGGY CODE ###

import collections

x = collections.deque(input())
n = int(input())

for i in range(n):
    y = input().split()
    if len(y) == 1:
      x.reverse()
    else:
      if int(y[1]) == 2:
          x.append(y[2])
      else:
          x.appendleft(y[2])

print("".join(x))

### FIXED CODE ###

import collections

x = collections.deque(input())
n = int(input())
rev = False

for i in range(n):
    y = input().split()
    if len(y) == 1:
      rev = not rev
    elif rev:
      if int(y[1]) == 2:
          x.appendleft(y[2])
      else:
          x.append(y[2])
    else:
      if int(y[1]) == 2:
          x.append(y[2])
      else:
          x.appendleft(y[2])

if rev:
  x.reverse()

print("".join(x))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

while True:
    try:
        n = int(raw_input())
        if n < 2:
            print(0)
            continue
        list1 = range(2, n + 1)
        list2 = []
        while True:
            i = list1.pop(0)
            list2.append(i)
            for x in list1:
                if x % i == 0:
                    list1.remove(x)
            if len(list1) == 0:
                break
            if i**2 > sorted(list1,lambda n1, n2:n2 - n1)[0]:
                break
        print(len(list2 + list1))
    except EOFError:
        break

### FIXED CODE ###

# -*- coding: utf-8 -*-

list = [1]*1000000
list[0] = 0
list[1] = 0
for i in range(1, 1000000):
    if list[i] == 1:
        for j in range(i**2, 1000000, i):
            list[j] = 0

for i in range(2, 1000000):
    list[i] += list[i -1]
while True:
    try:
        n = int(raw_input())
        print(list[n])
    except EOFError:
        break
### BUGGY CODE ###

n = int(input())
a_list = [int(input()) for _ in range(n)]
checked = []
num = 0
count = 0

while num not in checked:
    checked.append(num)
    num = a_list[num] - 1
    count += 1
    if num == 1:
        break

if num == 1:
    print(count)
else:
    print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a_tuple = tuple(int(input()) for _ in range(n))
num = 0
count = 0

for i in range(n):
    num = a_tuple[num] - 1
    count += 1
    if num == 1:
        break

if num == 1:
    print(count)
else:
    print(-1)
### BUGGY CODE ###

import sys
import numpy as np
n=int(input())
List=list(map(int,input().split()))
List=np.array(List)
if 0 in List:
    print(0)
    sys.exit()
ans=1
for i in List:
    ans*=int(i)
if ans<=10**18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

import sys
n=int(input())
List=list(map(int,input().split()))
List.sort(reverse=True)
if 0 in List:
    print(0)
    sys.exit()
ans=1
for i in List:
    if ans<=10**18:
        ans*=i
    else:
        print(-1)
        sys.exit()
if ans<=10**18:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

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

from itertools import combinations

c =list(combinations(Edges,3))

cnt =0
for i in c:
    e1=(i[1] + i[2])
    e2=(i[0] + i[2])
    e3=(i[0] + i[1])

    if i[0] < e1 and i[1] < e2 and i[2] < e3:
        cnt+=1

print(cnt)

### FIXED CODE ###

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

Edges=sorted(Edges)
cnt =0
# for i in c:
#     e1=(i[1] + i[2])
#     e2=(i[0] + i[2])
#     e3=(i[0] + i[1])

#     if i[0] < e1 and i[1] < e2 and i[2] < e3:
#         cnt+=1


import bisect

for a in range(N-2):
    for b in range(a+1,N-1):
        ab = Edges[a] + Edges[b]

        idx = bisect.bisect_left(Edges,ab)

        cnt += max(0,idx-b-1)


print(cnt)
### BUGGY CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
N, K = LI()
A = LI()


def main():
    ans = A.copy()
    w = [0] * (N + 1)
    for i in range(N):
        w[max(0, i - A[i])] += 1
        w[min(N, i + A[i] + 1)] -= 1
    
    for _ in range(K):
        x = 0
        l = [0] * (N + 1)
        for i in range(N):
            x += w[i]
            ans[i] = x
            l[max(0, i - x)] += 1
            l[min(N, i + x + 1)] -= 1
        w = l
    
    print(*ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
N, K = LI()
A = LI()


def main():
    ans = A.copy()
    w = [0] * (N + 1)
    for i in range(N):
        w[max(0, i - A[i])] += 1
        w[min(N, i + A[i] + 1)] -= 1
    
    for _ in range(K):
        x = 0
        l = [0] * (N + 1)
        flag = True
        for i in range(N):
            x += w[i]
            if x != N:
                flag = False
            ans[i] = x
            l[max(0, i - x)] += 1
            l[min(N, i + x + 1)] -= 1
        if flag:
            break
        w = l
    
    print(*ans)


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

n = int(raw_input())
s = map(int, raw_input().split())
m = int(raw_input())
t = map(int, raw_input().split())

count = 0
for i in t:
    if i in s:
        count += 1

print count

### FIXED CODE ###

n = int(raw_input())
s = map(int, raw_input().split())
m = int(raw_input())
t = map(int, raw_input().split())

s = list(set(s))
s.sort()
l = len(s)-1

count = 0
for i in t:
    low = 0
    high = l
    while low <= high:
        mid = (low+high)/2
        if s[mid] == i:
            count += 1
            break
        if s[mid] < i:
            low = mid+1
        else:
            high = mid-1

print count
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
from bisect import bisect_left

n = int(readline())
a = list(map(int,readline().split()))
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
que = deque()
L = [a[0]]
que.append((0,1,L))
chk = [False]*n
chk[0] = True
cnt = 1
ans = [1]*n
while que:
  now,m,L = que.popleft()
  if cnt == n:
    break
  for i in g[now]:
    if not chk[i]:
      ind = bisect_left(L,a[i])
      if m == ind:
        newm = m+1
        newL = L+[a[i]]
      else:
        newm = m
        newL = L[:ind]+[a[i]]+L[ind+1:]
      ans[i] = newm
      chk[i] = True
      cnt += 1
      que.append((i,newm,newL))

print(*ans,sep='\n')

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
from bisect import bisect_left

n = int(readline())
A = list(map(int,readline().split()))
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
que = deque()
inf = 10**9+1
dp = [inf]*n
que.append((0,-1))
chk = [False]*n
chk[0] = True
cnt = 0
ans = [1]*n

while que:
  now,d = que.pop()
  if d != -1:
    dp[now] = d
  else:
    ind = bisect_left(dp,A[now])
    que.append((ind,dp[ind]))
    dp[ind] = A[now]
    ans[now] = bisect_left(dp,inf)
    cnt += 1
    for i in g[now]:
      if not chk[i]:
        chk[i] = True
        que.append((i,-1))
  if cnt == n:
    break
        
print(*ans,sep='\n')
### BUGGY CODE ###

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

b_list = list(range(1, N+1))
c_list = []
for i in range(N):
    sr = b_list[i]
    g = int(a.count(sr))
    c_list.append(g)

for i in c_list:
    print(i)

### FIXED CODE ###

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

ans = [0]*N
for i in range(len(A)):
    tmp = A[i]
    ans[tmp-1] += 1


for a in ans:
    print(a)
### BUGGY CODE ###

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


def bellman_ford(s, g):
    # loop 0 - (n-1) : bellman ford
    # loop n - (2n-1): check g can be updated
    dist = [float("inf")] * n
    dist[s] = 0
    negative = [False] * n
    for i in range(2 * n):
        for a, b, c in abc:
            a -= 1
            b -= 1
            cost = -(c - p)

            if dist[b] > dist[a] + cost:
                dist[b] = dist[a] + cost
                if i >= n:
                    negative[b] = True

    if negative[g]:
        return -1

    else:
        return max(-dist[g], 0)


ans = bellman_ford(0, n - 1)
print(ans)


### FIXED CODE ###

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


def bellman_ford(s, g):
    # loop 0 - (n-1) : bellman ford
    # loop n - (2n-1): check g can be updated
    dist = [float("inf")] * n
    dist[s] = 0
    for i in range(2 * n):
        for a, b, c in abc:
            a -= 1
            b -= 1
            cost = -(c - p)

            if dist[b] > dist[a] + cost:
                dist[b] = dist[a] + cost
                if i >= n:
                    dist[b] = -float("inf")

    if dist[g] == -float("inf"):
        return -1

    else:
        return max(-dist[g], 0)


ans = bellman_ford(0, n - 1)
print(ans)
### BUGGY CODE ###

class ColorMgmt:
    def __init__(self, n):
        self.colors_hash = [set() for _ in range(n)]
        self.next_colors = [1] * n
    
    def set_color(self, v, c):
        self.colors_hash[v].add(c)
        cnt = 1
        while cnt in self.colors_hash[v]:
            cnt += 1
        self.next_colors[v] = cnt
    
    def get_color(self, v):
        return self.next_colors[v]


N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for _ in range(N)]
edge_cnt = [0] * N
for idx, (a, b) in enumerate(ab):
    a, b = a-1, b-1
    edge[a].append([b, a, 0, idx])
    edge_cnt[a] += 1
    edge_cnt[b] += 1
K = max(edge_cnt)

next_list = []
now_list = [0]
color_mgmt = ColorMgmt(N)
while len(now_list) > 0:
    for v in now_list:
        for idx, nextv in enumerate(edge[v]):
            if v == nextv[0]:
                continue
            colors1 = color_mgmt.get_color(nextv[1])
            colors2 = color_mgmt.get_color(nextv[0])
            color = max(colors1, colors2)
            color_mgmt.set_color(nextv[1], color)
            color_mgmt.set_color(nextv[0], color)
            edge[v][idx][2] = color
            next_list.append(nextv[0])
    
    now_list = list(next_list)
    next_list = []

ret = []
for edges in edge:
    for e in edges:
        ret.append(e)
ret.sort(key=lambda x:x[3])
print(K)
for r in ret:
    print(r[2])


### FIXED CODE ###

class ColorMgmt:
    from heapq import heappop, heappush
    def __init__(self, n):
        self.colors_hash = [set() for _ in range(n)]
        self.next_colors = [1] * n
    
    def set_color(self, v, c):
        self.colors_hash[v].add(c)
        while self.next_colors[v] in self.colors_hash[v]:
            self.next_colors[v] += 1
    
    def get_color(self, v):
        return self.next_colors[v]


N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for _ in range(N)]
edge_cnt = [0] * N
for idx, (a, b) in enumerate(ab):
    a, b = a-1, b-1
    edge[a].append([b, a, 0, idx])
    edge_cnt[a] += 1
    edge_cnt[b] += 1
K = max(edge_cnt)

next_list = []
now_list = [0]
color_mgmt = ColorMgmt(N)
while len(now_list) > 0:
    for v in now_list:
        for idx, nextv in enumerate(edge[v]):
            if v == nextv[0]:
                continue
            colors1 = color_mgmt.get_color(nextv[1])
            colors2 = color_mgmt.get_color(nextv[0])
            color = max(colors1, colors2)
            color_mgmt.set_color(nextv[1], color)
            color_mgmt.set_color(nextv[0], color)
            edge[v][idx][2] = color
            next_list.append(nextv[0])
    
    now_list = list(next_list)
    next_list = []

ret = []
for edges in edge:
    for e in edges:
        ret.append(e)
ret.sort(key=lambda x:x[3])
print(K)
for r in ret:
    print(r[2])
### BUGGY CODE ###

s = input()
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
d = 0

for c in s[::-1]:
    if d == 0:
        d += 1
        if c == "?":
            for i in range(10):
                table[1][i] = 1
        else:
            table[1][int(c)] = 1
        continue

    if c == "?":
        for n in range(10):
            for i in range(13):
                table[d + 1][(i + n * 10 ** d) % 13] += table[d][i]

    else:
        for i in range(13):
            table[d + 1][(i + int(c) * 10 ** d) % 13] += table[d][i]
    d += 1

print(table[d][5] % mod)

### FIXED CODE ###

s = input()
s = s[::-1]
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
table[0][0] = 1
dd = 1
for c in range(len(s)):
    if s[c] == "?":
        for n in range(10):
            for i in range(13):
                table[c + 1][(i + n * dd) % 13] += table[c][i]
                table[c + 1][(i + n * dd) % 13] %= mod
    else:
        num = int(s[c])
        for i in range(13):
            table[c + 1][(i + num * dd) % 13] += table[c][i]
            table[c + 1][(i + num * dd) % 13] %= mod
    dd = (dd * 10) % 13
print(table[c + 1][5])
### BUGGY CODE ###

import math

n, m = map(int, input().split())
mod = 10**9+7

def prime_decomposition(n):
    p = 2
    prime = {}
    while n!=1:
        while n%p == 0:
            n = n/p
            if p not in prime:
                prime[p] = 0
            prime[p] += 1
        p += 1
    return prime

primes = prime_decomposition(m)
# print(primes)
ans = 1

def combination(n,k):
    ret1 = 1
    ret2 = 1
    for i in range(k):
        ret1 *= n-i
        ret2 *= k-i
    return ret1//ret2

for p in primes:
    comb = combination(primes[p]+n-1, primes[p])
    ans *= comb
    ans %= mod

print(int(ans))


### FIXED CODE ###

n, m = map(int, input().split())
mod = 10**9+7

def prime_decomposition(n):
    p = 2
    prime = {}
    while n!=1:
        while n%p == 0:
            n = n//p
            if p not in prime:
                prime[p] = 0
            prime[p] += 1
        p += 1
    return prime

primes = prime_decomposition(m)
# print(primes)
ans = 1

def combination(n,k):
    ret1 = 1
    ret2 = 1
    for i in range(k):
        ret1 *= n-i
        ret2 *= k-i
    return ret1//ret2

for pw in primes.values():
    comb = combination(pw+n-1, pw)
    ans *= comb
    ans %= mod

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

import numpy as np
n,m = [int(i) for i in input().split()]

pair=np.array([list(map(lambda x:int(x)-1,input().split())) for _ in range(m)])
graph=np.array([[0]*n for i in range(n)])

def dfs(v):
    if visited[v]:
        return
    visited[v]=True
    for j in [k for k,v2 in enumerate(graph[v]) if v2 == 1]:
        dfs(j)


for p in pair:
    graph[p[0]][p[1]] = graph[p[1]][p[0]] = 1
#print(graph)  
for i in range(m):
    ans=0
    x,y = pair[i]
    graph[x][y] = graph[y][x] = 0

    for i in range(n):
        visited=[False]*n
        dfs(i)
        #print(visited)
        ans += sum([1 for j in visited[i:] if not j]) 
        
    print(ans)

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1 for _ in range(n+1)]

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    
def main():
    N, M = [int(_) for _ in input().split()]
    bridge = [tuple(map(int, input().split())) for _ in range(M)]

    last = []
    last.append(int(N * (N-1) * 0.5))

    ins = UnionFind(N)
    last_temp = 0

    for i in range(M-1):
        #print(ins.par)
        if ins.same_check(bridge[M-1-i][0],bridge[M-1-i][1]):
            last.append(last[-1])
            #ins.union(bridge[M-1-i][0],bridge[M-1-i][1])
        else:
            last_temp = last[-1] - (ins.size[ins.find(bridge[M-1-i][0])]) * (ins.size[ins.find(bridge[M-1-i][1])])
            #print(ins.size,i)
            last.append(last_temp)
            ins.union(bridge[M-1-i][0],bridge[M-1-i][1])
    
    [print(last[M-i-1]) for i in range(M)]
    exit()
    
main()
### BUGGY CODE ###

n, m, q = map(int, input().split())
x = [[0 for i in range(n + 1)] for j in range(n + 1)]
c = [[0 for i in range(n + 1)] for j in range(n + 1)]
for i in range(m):
    l, r = map(int, input().split())
    c[l][r] += 1
for i in range(1, n + 1):
    for j in range(1, n + 1):
        x[i][j] = x[i][j - 1] + c[i][j]
for k in range(q):
    ans = 0
    p, q2 = map(int, input().split())
    for i in range(p, q2 + 1):
        ans += x[i][q2] - x[i][p - 1]
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, m, q = map(int, input().split())
x = [[0 for i in range(n + 1)] for j in range(n + 1)]
c = [[0 for i in range(n + 1)] for j in range(n + 1)]
for i in range(m):
    l, r = map(int, input().split())
    c[l][r] += 1
for i in range(1, n + 1):
    for j in range(1, n + 1):
        x[i][j] = x[i][j - 1] + c[i][j]
for k in range(q):
    ans = 0
    p, q2 = map(int, input().split())
    for i in range(p, q2 + 1):
        ans += x[i][q2] - x[i][p - 1]
    print(ans)
### BUGGY CODE ###

X,Y,Z,K = map(int, input().split())
A = sorted(list(map(int, input().split())),reverse=True)
B = sorted(list(map(int, input().split())),reverse=True)
C = sorted(list(map(int, input().split())),reverse=True)

D = [[0,0,0]]
used = []
ans = []
for k in range(K):
  #print(k,D)
  mxd = 0
  mxi = 0
  for i in range(len(D)):
    d = A[D[i][0]]+B[D[i][1]]+C[D[i][2]]
    if d >= mxd:
      mxd = d
      mxi = i
  ans.append(mxd)
  if D[mxi][0]+1 < X and [D[mxi][0]+1,D[mxi][1],D[mxi][2]] not in D and [D[mxi][0]+1,D[mxi][1],D[mxi][2]] not in used:
    D.append([D[mxi][0]+1,D[mxi][1],D[mxi][2]])
  if D[mxi][1]+1 < Y and [D[mxi][0],D[mxi][1]+1,D[mxi][2]] not in D and [D[mxi][0],D[mxi][1]+1,D[mxi][2]] not in used:
    D.append([D[mxi][0],D[mxi][1]+1,D[mxi][2]])
  if D[mxi][2]+1 < Z and [D[mxi][0],D[mxi][1],D[mxi][2]+1] not in D and [D[mxi][0],D[mxi][1],D[mxi][2]+1] not in used:
    D.append([D[mxi][0],D[mxi][1],D[mxi][2]+1])
  used.append(D[mxi])
  del D[mxi]
#print(D)
for a in ans:
  print(a)


### FIXED CODE ###

X,Y,Z,K = map(int, input().split())
A = sorted(list(map(int, input().split())),reverse=True)
B = sorted(list(map(int, input().split())),reverse=True)
C = sorted(list(map(int, input().split())),reverse=True)

D = {(0,0,0)}
used = set()
ans = []
for k in range(K):
  #print(k,D)
  mxdsum = 0
  for d in D:
    dsum = A[d[0]]+B[d[1]]+C[d[2]]
    if dsum >= mxdsum:
      mxdsum = dsum
      mxd = d
  ans.append(mxdsum)
  if mxd[0]+1 < X and (mxd[0]+1,mxd[1],mxd[2]) not in used:
    D.add((mxd[0]+1,mxd[1],mxd[2]))
  if mxd[1]+1 < Y and (mxd[0],mxd[1]+1,mxd[2]) not in used:
    D.add((mxd[0],mxd[1]+1,mxd[2]))
  if mxd[2]+1 < Y and (mxd[0],mxd[1],mxd[2]+1) not in used:
    D.add((mxd[0],mxd[1],mxd[2]+1))
  used.add(mxd)
  D.remove(mxd)
#print(D)
for a in ans:
  print(a)
### BUGGY CODE ###

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

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
A = list(map(lambda x:-x, map(int, input().split())))
heapq.heapify(A)
for i in range(m):
    mx = heapq.heappop(A)
    heapq.heappush(A,mx/2)
print(sum([int(-a) for a in A]))
### BUGGY CODE ###

# https://atcoder.jp/contests/abc142/tasks/abc142_e
# このナップサックdpは面白い！
# 配るdpをイメージするとわかりやすい
# dp[i][bit] ... [0,i)の鍵を考慮したときに状態bitであるための最小の費用
# bitは開けられる宝箱を2進数で示している。5(101)だったら、0,2の宝箱が開けられる。
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def as_bit(ls):
    # 開けられる宝箱をbitで示す
    ret = 0
    for l in ls:
        ret ^= 1 << (l - 1)
    return ret


from itertools import product
INF = 10**9
N, M = read_ints()
C = []
A = []
for _ in range(M):
    a, b = read_ints()
    A.append(a)
    c = read_ints()
    C.append(as_bit(c))

'''
dp[i][bit] ... [0,i)の鍵を考慮したときに状態bitであるための最小の費用
bitは開けられる宝箱を2進数で示している。5(101)だったら、0,2の宝箱が開けられる。

更新則
dp[i+1][bit|C[i]] = min(dp[i+1][bit|C[i]], dp[i][bit] + A[i]) # i番目を取る
dp[i+1][bit] = min(dp[i+1][bit], dp[i][bit]) #i番目を取らない
∵配るDP。ナンプサックDPの重さの更新がbit演算に置き換わっただけ

初期条件&境界条件
dp[i][bit]=INF
dp[i][0]=0
'''

dp = [[INF] * (2 ** N) for _ in range(M + 1)]

for i in range(M + 1):
    dp[i][0] = 0

for i, bit in product(range(M), range(2 ** N)):
    dp[i + 1][bit | C[i]] = min(dp[i + 1][bit | C[i]], dp[i][bit] + A[i])
    dp[i + 1][bit] = min(dp[i + 1][bit], dp[i][bit])

ans = dp[-1][-1]
print(ans if ans != INF else -1)


### FIXED CODE ###

# https://atcoder.jp/contests/abc142/tasks/abc142_e
# このナップサックdpは面白い！
# 配るdpをイメージするとわかりやすい
# dp[i][bit] ... [0,i)の鍵を考慮したときに状態bitであるための最小の費用
# bitは開けられる宝箱を2進数で示している。5(101)だったら、0,2の宝箱が開けられる。
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def as_bit(ls):
    # 開けられる宝箱をbitで示す
    ret = 0
    for l in ls:
        ret ^= 1 << (l - 1)
    return ret


from itertools import product
INF = 10**9
N, M = read_ints()
C = []
A = []
for _ in range(M):
    a, b = read_ints()
    A.append(a)
    c = read_ints()
    C.append(as_bit(c))

'''
dp[i][bit] ... [0,i)の鍵を考慮したときに状態bitであるための最小の費用
bitは開けられる宝箱を2進数で示している。5(101)だったら、0,2の宝箱が開けられる。

更新則
dp[i+1][bit|C[i]] = min(dp[i+1][bit|C[i]], dp[i][bit] + A[i]) # i番目を取る
dp[i+1][bit] = min(dp[i+1][bit], dp[i][bit]) #i番目を取らない
∵配るDP。ナンプサックDPの重さの更新がbit演算に置き換わっただけ

初期条件&境界条件
dp[i][bit]=INF
dp[i][0]=0
'''

dp = [[INF] * (2 ** N) for _ in range(M + 1)]

for i in range(M + 1):
    dp[i][0] = 0

for i, bit in product(range(M), range(2 ** N)):
    dp[i + 1][bit | C[i]] = min(dp[i + 1][bit | C[i]], dp[i][bit] + A[i])
    dp[i + 1][bit] = min(dp[i + 1][bit], dp[i][bit])

ans = dp[-1][-1]
print(ans if ans != INF else -1)