Harryxun/stf_run huggingface dataset:
N,Ma,Mb = map(int,input().split())
abc = [list(map(int,input().split())) for _ in range(N)]
inf = 10**9
dp = [[inf for i in range(N*10)] for i in range(N*10)]
dp[0][0] = 0
max_a = 0
max_b = 0
for i in range(N):
    max_a += abc[i][0]
    max_b += abc[i][1]
    for ai in range(abc[i][0],max_a+1)[::-1]:
        for bi in range(abc[i][1],max_b+1)[::-1]:
            dp[ai][bi] = min(dp[ai][bi],dp[ai-abc[i][0]][bi-abc[i][1]]+abc[i][2])
ans = inf
for i in range(1,min(max_a//Ma,max_b//Mb)):
    ans = min(ans,dp[i*Ma][i*Mb])
if ans == inf:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N,Ma,Mb = map(int,input().split())
abc = [list(map(int,input().split())) for _ in range(N)]
inf = 10**9
dp = [[inf for i in range(N*10+1)] for i in range(N*10+1)]
dp[0][0] = 0
max_a = 0
max_b = 0
for i in range(N):
    max_a += abc[i][0]
    max_b += abc[i][1]
    for ai in range(abc[i][0],max_a+1)[::-1]:
        for bi in range(abc[i][1],max_b+1)[::-1]:
            dp[ai][bi] = min(dp[ai][bi],dp[ai-abc[i][0]][bi-abc[i][1]]+abc[i][2])
ans = inf
for i in range(1,min(max_a//Ma,max_b//Mb)):
    ans = min(ans,dp[i*Ma][i*Mb])
if ans == inf:
    print(-1)
else:
    print(ans)
n = int(input())
a = list(map(int, input().split()))

cnt = 1

increase = a[1] - a[0];
for i in range(2, len(a)):
    new_inc = a[i] - a[i-1];
    if increase * new_inc < 0:
        cnt += 1
        increase = 0
    elif increase == 0:
        increase = new_inc
print(cnt)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
if n < 3:
    print(1)
    exit(0)
cnt = 1

increase = a[1] - a[0];
for i in range(2, len(a)):
    new_inc = a[i] - a[i-1];
    if increase * new_inc < 0:
        cnt += 1
        increase = 0
    elif increase == 0:
        increase = new_inc
print(cnt)
import re

N, M = map(int, input().split())
S = str(input())
T = str(input())
#print(S)

# 最大公約数
def gcd(a, b):
  while b > 0:
    a, b = b, a%b
  return a

# 最小公倍数
def lcm(a, b):
  return a*b/gcd(a, b)

L = int(lcm(N, M))

#文字列の作成
#SをもとにX
X1 = r''
n = 0
for i in range(1,int(L)):
  if i == n * (L//N) + 1:
    X1 += S[n]
    n += 1
  else:
    X1 += r'*'
#print(X1)  
#X1とTを比べる
m = 0
ans = 0
for i in range(0,int(L)):
  if i == m * (L//M) :
    #print(i,m,X1[i],T[m])
    if X1[i] == T[m] or X1[i] == "*":
      ans = 1
      m += 1
    else:
      ans = -1
      break

if ans != -1:
  print(int(L))
else:
  print(-1)

### FIXED CODE ###

from fractions import gcd
from bisect import bisect_left
 
N, M = map(int, input().split())
S = input()
T = input()
 
if N > M:
    N, M = M, N
    S, T = T, S

G = N*M // gcd(N, M)
 
a = G//N
b = G//M
 
X = [a*i for i in range(N)]
Y = [b*j for j in range(M)]
 
for i, x in enumerate(X):
    j = bisect_left(Y, x)
    if j < M and Y[j] == x:
        if S[i] != T[j]:
            print(-1)
            break
else:
    print(G)
def lcd(a,b): ##return least common multiple of a and b
    if a > b:
        return lcd(a-b,b)
    elif a < b:
        return lcd(b-a,a)
    elif a == b:
        return a

a,b = input().split()
print(lcd(a,b))

### FIXED CODE ###

def lcd(a,b): ##return least common multiple of a and b
    if a > b:
        return lcd(a-b,b)
    elif a < b:
        return lcd(b-a,a)
    elif a == b:
        return a

a,b = map(int,input().split())
print(lcd(a,b))
from scipy.special import perm, comb
N,M=list(map(int,input().split()))
A=[int(input()) for i in range(M)]
A.append(N)
if not 1 in A:
    A.append(0)
    A.sort()
count=1
for m in range(len(A)-1):

    count*=sum([comb((A[m+1]-1)-A[m]-i,i,exact=True) for i in range((A[m+1]-1)-A[m])])
    #print(sum([comb((A[m+1]-1)-A[m]-i,i,exact=True) for i in range((A[m+1]-1)-A[m])]),count)
print(count%1000000007)


### FIXED CODE ###

N,M=map(int,input().split())
mod=10**9+7
A=set([int(input()) for i in range(M)])

data=[0 for i in range(N)]
if 1 not in A:
    data[0]=1
if N>=2:
    if 2 not in A:
        data[1]=1+data[0]


for i in range(2,N):
    if i+1 not in A:
        data[i]=data[i-1]+data[i-2]
        data[i]%=mod

#print(data)

print(data[-1])
#!/usr/bin/env python3

# input
n, m = map(int, input().split())
s = [-1 for _ in range(m)]
c = [-1 for _ in range(m)]
for i in range(m):
    s[i], c[i] = map(int, input().split())

# calc

# 重複があり、かつ、値が異なれば🙅
d = {}
for index, key in enumerate(s):
    if key not in d.keys():
        d[key] = c[index]
    else:
        if d[key] != c[index]:
            print(-1)
            exit(0)

# 0始まりは🙅
mi = min(list(d.keys()))
if d[mi] == 0:
    print(-1)
    exit(0)

# output
ans = ''
#import pdb; pdb.set_trace()
ma = max(list(d.keys()))
for i in range(1, ma+1):
    if i in d.keys():
        ans += str(d[i])
    else:
        ans += '0'
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
n, m = map(int, input().split())
s = [-1 for _ in range(m)]
c = [-1 for _ in range(m)]
for i in range(m):
    s[i], c[i] = map(int, input().split())

for x in range(1000):
    x = str(x)
    if len(x) != n:
        continue
    ok = True
#    print('x =', x)
    for i in range(m):
#        print('s[i] =', s[i])
#        print('x[s[i]-1] =', x[s[i]-1])
#        print('c[i] =', c[i])
        if x[s[i]-1] != str(c[i]):
            ok = False
    if ok: 
        print(x)
        exit(0)

print(-1)
# coding: utf-8
# Your code here!
N,M=map(int,input().split())

visited=[0]*N
frnds=[[] for i in range(N)]

for _ in range(M):
    a,b=map(int,input().split())
    frnds[a-1].append(b-1)
    frnds[b-1].append(a-1)

for i in range(N):
    frnds[i]=list(set(frnds[i]))

def saiki(num):
    value=1
    visited[num]=1
    for f in frnds[num]:
        if visited[f]!=1:
            value+=saiki(f)
    return value

ans=0
for i in range(N):
    if visited[i]!=1:
        ans=max(saiki(i),ans)

print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**7)

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

visited=[0]*N
frnds=[[] for i in range(N)]

for _ in range(M):
    a,b=map(int,input().split())
    frnds[a-1].append(b-1)
    frnds[b-1].append(a-1)

for i in range(N):
    frnds[i]=list(set(frnds[i]))

def saiki(num):
    value=1
    visited[num]=1
    for f in frnds[num]:
        if visited[f]!=1:
            value+=saiki(f)
    return value

ans=0
for i in range(N):
    if visited[i]!=1:
        ans=max(saiki(i),ans)

print(ans)
def main():
    inputList = input().split()
    print(int(inputList[0]) * int(inputList[1]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    A, B = map(int, input().replace(".", "").split())
    print(A*B//100)

if __name__ == "__main__":
    main()
import itertools

comb = list(itertools.product([_ for _ in range(-70, 140)],repeat=2))

for c in comb:
    a, b = c[0], c[1]
    if a**5 - b**5 == x:
        print(a, b)
        break

### FIXED CODE ###

import itertools
x = int(input())

comb = list(itertools.product([_ for _ in range(-70, 140)],repeat=2))

for c in comb:
    a, b = c[0], c[1]
    if a**5 - b**5 == x:
        print(a, b)
        break
n = int(input())
print(len(set(list(map(int, [input() for i in range(n+1)])))))

### FIXED CODE ###

n = int(input())
print(len(set(list(map(int, [input() for i in range(n)])))))
N,K = list(map(int,input().split()))

e_list = [[] for i in range(N)]

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

if K==1:
    print(1)
else:
    mod=10**9+7
    combA = [1]
    ca = 1
    for i in range(K-1):
        ca = (ca*(K-1-i))%mod
        combA.append(ca)
    combB = [1]
    cb = 1
    for i in range(K-2):
        cb = (cb*(K-2-i))%mod
        combB.append(cb)

    #print(combA)
    #print(combB)
    ans = K
    mod=10**9+7
    vi = 0 #時と場合によってここを変える
    from collections import deque
    Q = deque([vi])
    checked_list = [False for i in range(N)]
    checked_list[vi]=True
    while len(Q)>0:
        v = Q.pop()
        count=0
        for v1 in e_list[v]:
            if not checked_list[v1]:
                checked_list[v1]=True
                Q.appendleft(v1)
                count+=1
        
        if v==0:
            ans= (ans*combA[count])%mod
        else:
            ans= (ans*combB[count])%mod
            #print(count)

    print(ans)

### FIXED CODE ###

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

e_list = [[] for i in range(N)]

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

if K==1:
    if N==1:
        print(1)
    else:
        print(0)
else:
    mod=10**9+7
    combA = [1]
    ca = 1
    for i in range(K-1):
        ca = (ca*(K-1-i))%mod
        combA.append(ca)
    combB = [1]
    cb = 1
    for i in range(K-2):
        cb = (cb*(K-2-i))%mod
        combB.append(cb)
    flag=True
    #print(combA)
    #print(combB)
    ans = K
    mod=10**9+7
    vi = 0 #時と場合によってここを変える
    from collections import deque
    Q = deque([vi])
    checked_list = [False for i in range(N)]
    checked_list[vi]=True
    while len(Q)>0:
        v = Q.pop()
        count=0
        for v1 in e_list[v]:
            if not checked_list[v1]:
                checked_list[v1]=True
                Q.appendleft(v1)
                count+=1
        
        if v==0:
            if count<=K-1:
                ans= (ans*combA[count])%mod
            else:
                flag=False
                break
        else:
            if count<=K-2:
                ans= (ans*combB[count])%mod
                #print(count)
            else:
                flag=False
                break
    if flag:
        print(ans)
    else:
        print(0)
N, M = map(int, input().split())

broken_step = []
for _ in range(M):
    broken_step.append(int(input()))
    
mod = 1000000007

memo = [-1] * (N+1)

def step_memo(N):
    if N == 0:
        return 1
    if N == 1:
        return 1

    a = 1
    b = 1
    
    if N-1 in broken_step:
        a = 0
    elif N-2 in broken_step:
        b = 0
    elif N in broken_step:
        a = 0
        b = 0
        
    if memo[N] != -1:
        return memo[N]
    memo[N] =  (a * step_memo(N-1) + b * step_memo(N-2)) % mod
    return (a * step_memo(N-1) + b * step_memo(N-2)) % mod
  
print(step_memo(N))

### FIXED CODE ###

N, M = map(int, input().split())
import sys
sys.setrecursionlimit(10000000)

mod = 1000000007

memo = [-1] * (N+1)

for _ in range(M):
    broken_step = int(input())
    memo[broken_step] = 0
    
memo[0] = 1
if memo[1] == -1:
    memo[1] = 1

def step_memo(N):
    
    if memo[N] != -1:
        return memo[N]
    
    memo[N] =  (step_memo(N-1) + step_memo(N-2)) % mod
    return (step_memo(N-1) + step_memo(N-2)) % mod
  
print(step_memo(N))
N = int(input())
S = str(input())
T = str(input())
ans = ''
for i in range(N):
    ans = ans + S[i:i+1] + T[i:i+1]
print(ans)

### FIXED CODE ###

N = int(input())
Str_input = str(input())
S = Str_input.split()[0]
T = Str_input.split()[1]
ans = ''
for i in range(N):
    ans = ans + S[i:i+1] + T[i:i+1]
print(ans)
A, B = map(int, input().split())

ans1 = int(A *100// 8) 
ans2 = int(B *100 // 10)

if ans1 = ans2:
    print(ans1)

elif ans1 > ans2:
    ans2_2 = int((B+1) *100 // 10)
    list = [int(ans2)]

    for i in range(ans2+1,ans2_2):
        list.append(int(i)) 
    
    if int(ans1) in list:
        print(ans1)
    else:
        print(-1)
elif: ans1 < ans2:
    ans1_2 = int((A+1) *100 // 8)
    list = [int(ans1)]

    for i in range(ans1+1,ans1_2):
        list.append(int(i)) 
    
    if int(ans2) in list:
        print(ans2)
    else:
        print(-1)

### FIXED CODE ###

A, B = map(int, input().split())
ans1 = int(A *100// 8) 
ans2 = int(B *100 // 10)
ans1_2 = int((A+1) *100 // 8)
ans2_2 = int((B+1) *100 // 10)
list1 = []
list2 = []

for i in range(ans1,ans1_2):
    if int(i * 0.08) == A: 
        list1.append(int(i))
for j in range(ans2,ans2_2):
    if int(j * 0.1) == B:
        list2.append(int(j))
if list1[0] == list2[0]:
    print(list1[0])
elif list1[0] > list2[0]:
    if list1[0] in list2:
        print(list1[0])
    else:
        print(-1)
elif list1[0] < list2[0]:
    if list2[0] in list1:
        print(list2[0])
    else:
        print(-1)
N,M = map(int,input().split())
# AB_s = [list(map(int,input().split())) for _ in range(N)]
dicts = {i:[] for i in range(1,M+1)}
for _ in range(N):
    A,B = map(int,input().split())
    if A in dicts:
        dicts[A].append(B)
answer = 0
wages = []
for i in range(1,M+1):
    wages.extend(dicts[i])
    if wages:
        wages.sort()
        if len(wages) > M-i:
            wages[M-i:] = []
        answer += wages.pop()
print(answer)
# AB_s = sorted(AB_s, key=lambda x:-x[0])
# print(AB_s)

### FIXED CODE ###

import heapq
N,M = map(int,input().split())
AB_s = [list(map(int, input().split())) for _ in range(N)]
MAPperA = {i: [] for i in range(1,M+1)}
# 残り日数ごとのマップを作る
for i, AB in enumerate(AB_s):
    if AB[0] in MAPperA:
        MAPperA[AB[0]].append(AB[1])
excutableJobList = []
heapq.heapify(excutableJobList)
answer = 0
# 短期間でできる仕事からリストを作って追加してそーとして最大値を追加していく
for i in range(1,M+1):
    for j in MAPperA[i]:
        heapq.heappush(excutableJobList, j*-1)
    if excutableJobList:
        answer += heapq.heappop(excutableJobList) * -1
print(answer)
n,a=open(0);print(eval(a.replace(" ","+")+"-"+n))

### FIXED CODE ###

print(-int(input())+sum(map(int,input().split())))
n,m = list(map(int,input().split() ))
h = list(map(int,input().split() ))

aPrev=0
a,b=0,0
count=0

good = [True] * n # 要素n が全てTrueの配列
for im in range(m):
    a,b = list(map(int,input().split()))
    if h[a-1] > h[b-1]:
        good[b] = False
    elif h[b-1] > h[a-1]:
        good[a-1] = False
    else:
        good[a-1] = False
        good[b-1] = False

print(good.count(True)) #count(x) リスト中のxの数を返す



### FIXED CODE ###

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

 # 要素n が全てTrueの配列
good = [True] * n
for im in range(m):
    a,b = list(map(int,input().split()))
    if h[a-1] > h[b-1]:
        good[b-1] = False
    elif h[b-1] > h[a-1]:
        good[a-1] = False
    else:
        good[a-1] = False
        good[b-1] = False

#count(x) リスト中のxの数を返す
print(good.count(True))
a, b = map(int(input().split()))

valid = range(1, 10)
if a in valid and b in valid:
  print(a*b)
else:
  print(-1)

### FIXED CODE ###

a, b = map(int, input().split())

valid = range(1, 10)
if a in valid and b in valid:
    print(a*b)
else:
    print(-1)
import math
N, M = map(int, input().split())


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])

    if arr == [] and n != 1:
        arr.append([n, 1])

    return arr


mod = 10**9 + 7


def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル
for i in range(2, N + int(math.log(M)+1) + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)


primes = factorization(M)
# 何箇所に分けるか（cnt以下）,その中でどう分けるか（しきりをどこにおくか（振り分けられないものが出ると選べれないのとおなじになるので、cnt - 選んだ数））
if N == 1:
    print(1)
    exit(0)
ans = 1

for p, cnt in primes:
    tmp = cmb(N+cnt-1, N-1, mod)
    ans *= tmp
    ans %= mod

print(ans)


### FIXED CODE ###

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


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


mod = 10**9 + 7


def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)


primes = factorization(M)
# 何箇所に分けるか（cnt以下）,その中でどう分けるか（しきりをどこにおくか（振り分けられないものが出ると選べれないのとおなじになるので、cnt - 選んだ数））

if N == 1 or M == 1:
    print(1)
    exit(0)
ans = 1
for p, cnt in primes:
    tmp = 0
    for i in range(1, min(cnt, N)+1):
        tmp += cmb(N, i, mod) * cmb(cnt-1, i-1, mod)
        #print(tmp, p, cnt, i)
        tmp %= mod
    ans *= tmp
    ans %= mod

print(ans)
n, m = [int(c) for c in input().split()]
 
k = [list(map(int, input().split())) for _ in range(n)]
 
food_count = [0] * m
 
for p in k:
    for i in range(1, len(p)):
        food_count[p[i]-1] += 1
 
count = 0
for f in food_count:
    if f == n:
        count += 1
 
print(count)


### FIXED CODE ###

a,b = map(int, input().split())
if b%a == 0:
    print(a+b)
else:
    print(b-a)
S = input()
K = int(input())

s = [v for v in S]

block = []
count = 1

for i in range(len(s)-1):
    if s[i] == s[i+1]:
        count += 1
        if i+2 == len(s):
            block.append(s[i]*count)
    else:
        block.append(s[i]*count)
        count = 1

z = len(block)
t = 0
d = 0

if not z == 1:
    for j in range(len(block)):
        x = len(block[j])
        if x == 1:
            continue
        else:
            if x%2 == 0:
                t += x//2
            elif x%2 == 1:
                t += x - (x+1)//2
    
    if block[0][0] == block[-1][-1]:
        joint = block[0] + block[-1]
        y = len(joint)
        if y%2 == 1:
            d = 0
        if y%2 == 0:
            d = 1
else:
    p = len(block[0])
    if p%2 == 0:
        t = p//2
    else:
        t = (p-1)//2
        if K%2 == 1:
            ans = t + p*(K-1)//2                       
            print(ans)
            exit()
        else:
            ans = p + p*(K-2)//2
            print(ans)
            exit()

ans = t*K + d*(K-1)
print(int(ans))

### FIXED CODE ###

S = input()
K = int(input())

s = [v for v in S]

block = []
count = 1

if len(s) == 1:
    if K == 1:
        print(0)
        exit()
    else:
        if K%2 == 1:
            print((K-1)//2)
            exit()
        else:
            print(K//2)
            exit()

for i in range(len(s)-1):
    if s[i] == s[i+1]:
        count += 1
        if i+2 == len(s):
            block.append(s[i]*count)
    else:
        block.append(s[i]*count)
        count = 1

z = len(block)
t = 0
d = 0

if not z == 1:
    for j in range(len(block)):
        x = len(block[j])
        if x == 1:
            continue
        else:
            if x%2 == 0:
                t += x//2
            elif x%2 == 1:
                t += x - (x+1)//2
    
    if block[0][0] == block[-1][-1]:
        joint = block[0] + block[-1]
        y = len(joint)
        if y%2 == 1:
            d = 0
        else:
            d = 1
else:
    p = len(block[0])
    if p%2 == 0:
        t = p//2
    else:
        t = (p-1)//2
        if K%2 == 1:
            ans = t + p*(K-1)//2                       
            print(ans)
            exit()
        else:
            ans = p + p*(K-2)//2
            print(ans)
            exit()

ans = t*K + d*(K-1)
print(ans)
import sys
sys.setrecursionlimit(10 ** 7)

import numpy as np
from heapq import *

X, Y, Z, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
B = np.array(list(map(int, input().split())))
C = np.array(list(map(int, input().split())))

# 二分探索でK個の選び方を探す
up = 10 ** 10 + 1 # 不可能
low = 0 # 可能
while up > low + 1:
    mid = (up+low)// 2
    if (A >= A.max() - mid).sum() * (B >= B.max() - mid).sum() * (C >= C.max() - mid).sum() >= K:
        low = mid
    else:
        up = mid
A_line = A.max() - low
B_line = B.max() - low
C_line = C.max() - low
A = [x for x in A if x >= A_line]
B = [x for x in B if x >= B_line]
C = [x for x in C if x >= C_line]
L = []
heapify(L)
for a in A:
    for b in B:
        for c in C:
            heappush(L, -(a+b+c))
for i in range(K):
    n = heappop(L)
    print(-n)

        


### FIXED CODE ###

import numpy as np
from heapq import *

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

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

h = []
heappush(h, (-A[0]-B[0]-C[0], 0, 0, 0))
used = set()
result = []

for _ in range(K):
    sum, i, j, k = heappop(h)
    result.append(-sum)
    if i < X-1 and (i+1, j, k) not in used:
        heappush(h, (-A[i+1]-B[j]-C[k], i+1, j, k))
        used.add((i+1, j, k))
    if j < Y-1 and (i, j+1, k) not in used:
        heappush(h, (-A[i]-B[j+1]-C[k], i, j+1, k))
        used.add((i, j+1, k))
    if k < Z-1 and (i, j, k+1) not in used:
        heappush(h, (-A[i]-B[j]-C[k+1], i, j, k+1))
        used.add((i, j, k+1))

for v in result:
    print(v)
N, M = map(int, input().split())
slist = [list(map(int, input().split()))[1:] for _ in range(M)]
plist = list(map(int, input().split()))

def count_on_switch(switch_array: list, on: set):
    return sum([int(sw in on) for sw in switch_array])

ans: int = 0
# print("---")
for i in range(2**N):
    on = set()
    for j in range(N):
        if ((i >> j) & 1):
             on.add(j+1)
    temp = 0
    for _ in range(M):
        cou_on = count_on_switch(slist[_], on)
        # print(i, cou_on)
        if cou_on % 2 != plist[_]:
            break
    else:
        ans += 1
print(ans)


### FIXED CODE ###

from copy import deepcopy
N,M = map(int,input().split())
s_list = []
for _ in range(M):
    s_list.append(tuple(map(int,input().split()[1:])))
plist = tuple(map(int,input().split()))

counter = 0
TF = [0]*N
TFlist = []
def make_bbb(long,number):
    b_n = bin(number)[2:]
    bbb = "0"*(long-len(b_n))+b_n
    return bbb
for _ in range(2**N):
    number = list(map(int,list(make_bbb(N,_))))
    TFlist.append(number)


for TF in TFlist:
    flg = False
    ok = 0
    for num,s in enumerate(s_list):
        sum_on = 0
        #各スイッチ
        for ele in s:
            sum_on += TF[ele-1]
        if sum_on%2 != plist[num]:
            flg = False
            break
        else:
            ok += 1
    if ok == M:
        counter += 1


print(counter)
import copy

def nC2(n):
    if n < 2:
        return 0
    else:
        return n*(n-1)//2

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

count = 0
B = copy.copy(A)
Num = list(set(B))
for num in Num:
    count += nC2(B.count(num))
#print(count)

for k in range(n):
    B = copy.copy(A)
    num = B.pop(k)
#    print()
#    print(k, num, B)
    print(countAll - B.count(num))

### FIXED CODE ###

import copy
from collections import Counter

l = ['a', 'a', 'a', 'a', 'b', 'c', 'c']
c = Counter

def nC2(n):
    if n < 2:
        return 0
    else:
        return n*(n-1)//2

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

count = 0
C = Counter(A)
for num in C.values():
    count += num*(num-1)//2
#print(count)

for a in A:
    print(count - (C[a] - 1))
N,L = map(int,input().split())

for n in range(int(N)):
    data.append(input())


    
result=sorted(data)

### FIXED CODE ###

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

data=[]
for n in range(int(N)):
    data.append(input())
  
iroha=""
A=sorted(data)
for i in A:
    iroha+=i
    
print(iroha)