A company of $n$ friends wants to order exactly two pizzas. It is known that in total there are $9$ pizza ingredients in nature, which are denoted by integers from $1$ to $9$.

Each of the $n$ friends has one or more favorite ingredients: the $i$-th of friends has the number of favorite ingredients equal to $f_i$ ($1 \le f_i \le 9$) and your favorite ingredients form the sequence $b_{i1}, b_{i2}, \dots, b_{if_i}$ ($1 \le b_{it} \le 9$).

The website of CodePizza restaurant has exactly $m$ ($m \ge 2$) pizzas. Each pizza is characterized by a set of $r_j$ ingredients $a_{j1}, a_{j2}, \dots, a_{jr_j}$ ($1 \le r_j \le 9$, $1 \le a_{jt} \le 9$) , which are included in it, and its price is $c_j$.

Help your friends choose exactly two pizzas in such a way as to please the maximum number of people in the company. It is known that a person is pleased with the choice if each of his/her favorite ingredients is in at least one ordered pizza. If there are several ways to choose two pizzas so as to please the maximum number of friends, then choose the one that minimizes the total price of two pizzas.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($1 \le n \le 10^5, 2 \le m \le 10^5$) — the number of friends in the company and the number of pizzas, respectively.

Next, the $n$ lines contain descriptions of favorite ingredients of the friends: the $i$-th of them contains the number of favorite ingredients $f_i$ ($1 \le f_i \le 9$) and a sequence of distinct integers $b_{i1}, b_{i2}, \dots, b_{if_i}$ ($1 \le b_{it} \le 9$).

Next, the $m$ lines contain pizza descriptions: the $j$-th of them contains the integer price of the pizza $c_j$ ($1 \le c_j \le 10^9$), the number of ingredients $r_j$ ($1 \le r_j \le 9$) and the ingredients themselves as a sequence of distinct integers $a_{j1}, a_{j2}, \dots, a_{jr_j}$ ($1 \le a_{jt} \le 9$).


-----Output-----

Output two integers $j_1$ and $j_2$ ($1 \le j_1,j_2 \le m$, $j_1 \ne j_2$) denoting the indices of two pizzas in the required set. If there are several solutions, output any of them. Pizza indices can be printed in any order.


-----Examples-----
Input
3 4
2 6 7
4 2 3 9 5
3 2 3 9
100 1 7
400 3 3 2 5
100 2 9 2
500 3 2 9 5

Output
2 3

Input
4 3
1 1
1 2
1 3
1 4
10 4 1 2 3 4
20 4 1 2 3 4
30 4 1 2 3 4

Output
1 2

Input
1 5
9 9 8 7 6 5 4 3 2 1
3 4 1 2 3 4
1 4 5 6 7 8
4 4 1 3 5 7
1 4 2 4 6 8
5 4 1 9 2 8

Output
2 4

Difficulty: HARD
Tags: Bit manipulation

Complete search
Skill types: Bit manipulation

Complete search

Starter code:

Solutions:
import sys
import math
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
ma = int(10000000000000000)
(n, m) = map(int, input().split())
a = [ma] * 515
a1 = [ma] * 515
fr = [0] * 515
pos = [0] * 515
for i in range(n):
	b = I()
	x = int(0)
	for j in range(1, b[0] + 1):
		b[j] -= 1
		x |= 1 << b[j]
	fr[x] += 1
min1 = int(ma)
max1 = int(0)
(ind, ind1) = (int(), int())
for i in range(m):
	b = I()
	x = int(0)
	for j in range(2, b[1] + 2):
		b[j] -= 1
		x |= 1 << b[j]
	if a[x] != ma:
		if fr[x] > max1:
			max1 = fr[x]
			min1 = a[x] + b[0]
			ind = pos[x]
			ind1 = i + 1
		elif fr[x] == max1:
			if b[0] + a[x] < min1:
				min1 = b[0] + a[x]
				ind = pos[x]
				ind1 = i + 1
	if a[x] > b[0]:
		a[x] = b[0]
		pos[x] = i + 1
for i in range(1, 512):
	for j in range(1, 512):
		if i == j or a[i] == ma or a[j] == ma:
			continue
		k = i | j
		cnt = int(0)
		while k > 0:
			cnt += fr[k]
			k = k - 1 & (i | j)
		if cnt > max1:
			ind = pos[i]
			ind1 = pos[j]
			max1 = cnt
			min1 = a[i] + a[j]
		if cnt == max1:
			if a[i] + a[j] < min1:
				ind = pos[i]
				ind1 = pos[j]
			min1 = min(min1, a[i] + a[j])
print(ind, ind1, sep=' ')


from sys import stdin, stdout
import itertools
(n, m) = map(int, stdin.readline().split())
friends = [0] * 512
exists = [0] * 512
costs_min = [0] * 512
costs_2 = [0] * 512
index_min = [0] * 512
index_2 = [0] * 512
count_friends = [0] * 512

def top_to_idx(top):
	ans = 0
	for t in top:
		ans += 1 << t - 1
	return ans

def idx_to_top(idx):
	ans = []
	for i in range(9):
		if idx & 1 << i:
			ans.append(i + 1)
	return ans
for i in range(n):
	top = list(map(int, stdin.readline().split()))[1:]
	friends[top_to_idx(top)] += 1

def subset(i, j):
	for s in range(9):
		if i & 1 << s and (not j & 1 << s):
			return False
	return True
for i in range(512):
	for j in range(512):
		if subset(j, i):
			count_friends[i] += friends[j]
for i in range(m):
	pizza = list(map(int, stdin.readline().split()))
	top_idx = top_to_idx(pizza[2:])
	cost = pizza[0]
	exists[top_idx] = True
	if costs_min[top_idx] == 0 or cost < costs_min[top_idx]:
		costs_2[top_idx] = costs_min[top_idx]
		index_2[top_idx] = index_min[top_idx]
		costs_min[top_idx] = cost
		index_min[top_idx] = i + 1
	elif costs_2[top_idx] == 0 or cost < costs_2[top_idx]:
		costs_2[top_idx] = cost
		index_2[top_idx] = i + 1
best_matches = -1
best_cost = -1
best = None
for p1 in range(512):
	for p2 in range(p1, 512):
		if not exists[p1] or not exists[p2]:
			continue
		if p1 == p2 and index_2[p1] == 0:
			continue
		p = p1 | p2
		matches = count_friends[p]
		cost = costs_min[p1] + costs_min[p2] if p1 != p2 else costs_min[p1] + costs_2[p2]
		if best_matches == -1 or matches > best_matches or (matches == best_matches and cost < best_cost):
			best = (index_min[p1], index_min[p2]) if p1 != p2 else (index_min[p1], index_2[p2])
			best_matches = matches
			best_cost = cost
print(best[0], best[1])


import os
import string
from math import inf
from functools import lru_cache
if os.getcwd() == 'C:\\Users\\User\\Desktop\\python\\Prog\\CodeForces' or os.environ['COMPUTERNAME'] == 'USER145':
	import pdb
	import sys
	pdb = pdb.Pdb(stdin=sys.stdin, stdout=sys.stdout)
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	from pprint import pprint
	from hypothesis import given, settings
	from hypothesis import strategies as st

def ri():
	return [int(i) for i in input().split()]

def to_bits(l):
	ans = 0
	for i in l:
		ans |= 1 << i - 1
	return ans
user_masks = [0 for i in range(1 << 10)]
pizzas = [[] for i in range(1 << 10)]

@lru_cache()
def count_sat_users(mask):
	ans = 0
	cmask = mask
	while cmask:
		ans += user_masks[cmask]
		cmask = cmask - 1 & mask
	return ans

def main():
	(n, m) = ri()
	for _ in range(n):
		(k, *a) = ri()
		bits = to_bits(a)
		user_masks[bits] += 1
	ans = (float(-inf), float(inf), -1, -1)
	for i in range(m):
		(c, k, *a) = ri()
		bits = to_bits(a)
		pizzas[bits].append((c, i + 1, bits))
		pizzas[bits].sort()
		while len(pizzas[bits]) > 2:
			pizzas[bits].pop()
	for mask_F in range(1 << 9):
		for mask_S in range(1 << 9):
			if len(pizzas[mask_F]) and len(pizzas[mask_S]) and (mask_F != mask_S):
				mask = mask_F | mask_S
				satisfied_users = count_sat_users(mask)
				f_pizza = next(iter(pizzas[mask_F]))
				s_pizza = next(iter(pizzas[mask_S]))
				summary_cost = 0
				summary_cost += f_pizza[0]
				summary_cost += s_pizza[0]
				ans = max(ans, (satisfied_users, -summary_cost, s_pizza[1], f_pizza[1]))
				bmask = mask
				while bmask:
					satisfied_users += user_masks[bmask]
					bmask = bmask - 1 & mask
			if len(pizzas[mask_F]) == 2:
				satisfied_users = count_sat_users(mask_F)
				it = iter(pizzas[mask_F])
				f_pizza = next(it)
				s_pizza = next(it)
				summary_cost = 0
				summary_cost += f_pizza[0] + s_pizza[0]
				ans = max(ans, (satisfied_users, -summary_cost, s_pizza[1], f_pizza[1]))
			if len(pizzas[mask_S]) == 2:
				satisfied_users = count_sat_users(mask_S)
				it = iter(pizzas[mask_S])
				f_pizza = next(it)
				s_pizza = next(it)
				summary_cost = 0
				summary_cost += f_pizza[0] + s_pizza[0]
				ans = max(ans, (satisfied_users, -summary_cost, s_pizza[1], f_pizza[1]))
	aans = [ans[2], ans[3]]
	aans.sort()
	print(*aans, sep=' ')
main()


import sys

def popcount(i):
	assert 0 <= i < 4294967296
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24
(N, M) = map(int, sys.stdin.readline().split())
table = [0] * 2 ** 9
for _ in range(N):
	S = tuple(map(int, sys.stdin.readline().split()))
	table[sum((2 ** (a - 1) for a in S[1:]))] += 1
dp = [0] * 2 ** 9
for s in range(2 ** 9):
	ppc = popcount(s)
	res = table[s]
	t = s & s - 1
	for _ in range(2 ** ppc - 1):
		res += table[t]
		t = t - 1 & s
	dp[s] = res
table = [False] * 2 ** 9
cost = [[] for _ in range(2 ** 9)]
idx = [[] for _ in range(2 ** 9)]
for i in range(M):
	T = tuple(map(int, sys.stdin.readline().split()))
	x = sum((2 ** (a - 1) for a in T[2:]))
	table[x] = True
	cost[x].append(T[0])
	idx[x].append(i + 1)
minidx = [cost[x].index(min(cost[x])) if cost[x] else -1 for x in range(2 ** 9)]
mincost = [10 ** 10] * 2 ** 9
mincostidx = [(0, 0) for _ in range(2 ** 9)]
reachable = [False] * 2 ** 9
for i in range(2 ** 9):
	if not table[i]:
		continue
	for j in range(2 ** 9):
		if not table[j]:
			continue
		reachable[i | j] = True
		if i != j:
			mi = min(cost[i])
			mj = min(cost[j])
			if mincost[i | j] > mi + mj:
				mincost[i | j] = mi + mj
				mincostidx[i | j] = (idx[i][minidx[i]], idx[j][minidx[j]])
ctr = -1
candi = []
for i in range(2 ** 9):
	if not reachable[i]:
		continue
	if ctr > dp[i]:
		continue
	elif ctr == dp[i]:
		candi.append(i)
	else:
		ctr = dp[i]
		candi = [i]
ans = 10 ** 11
Ans = (-1, -1)
for c in candi:
	if table[c] and len(cost[c]) > 1:
		D = cost[c][:]
		res = min(D)
		a = D.index(res)
		D.remove(res)
		r = min(D)
		b = D.index(r)
		if cost[c][b] != r:
			b += 1
		if a == b:
			b += 1
		res += r
		if ans > res:
			ans = res
			Ans = (idx[c][a], idx[c][b])
	if ans > mincost[c]:
		ans = mincost[c]
		Ans = mincostidx[c]
print(*Ans)