Two Pizzas

题意翻译

【题目描述】 现在到了午饭时间，你要为$n$个朋友定披萨。 众所周知，披萨的原料分为9种。每位朋友都有自己喜好的原料（一种或多种），第$i$个朋友喜欢的原料有$f_i$种，分别是$b_{i1},b{i2},...,b{if_i}$。 披萨店出售$m$种不同的披萨。第$j$种披萨里面有$r_j$种原料，分别是$a_{j1},a_{j2},...,a_{jr_j}$。第$j$种披萨售价为$c_j$。 现在你们决定购买恰好两个披萨。我们称一个人是“满意的”，当且仅当他/她想要的**每种原料**都在**至少一个**买下来的披萨出现。你希望最多人是“满意的”，并在这个前提下，支出越少越好。请输出任意一种方案。 【输入格式】 第一行，两个正整数$n,m$，分别代表人数和披萨种数。 接下来$n$行，每行描述一个人的口味，先是一个正整数$f_i$，接下来$f_i$个正整数$b_{i1},b{i2},...,b{if_i}$，含义如题所示。 接下来$m$行，每行描述一种披萨。先是两个正整数$c_j,r_j$，接下来$r_j$个正整数$a_{j1},a_{j2},...,a_{jr_j}$，含义如题所示。 【输出格式】 一行，两个正整数$j_1.j_2$，代表所买的两个披萨。以任意顺序输出任意方案均可。 【数据范围与约定】 保证： - $1\leq n\leq 10^5,2\leq m\leq 10^5$ - $1\leq c_j\leq 10^9$ - $1\leq f_i,b_{it},r_j,a_{jt}\leq 9$

题目描述

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.

输入输出格式

输入格式

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 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.

输入输出样例

输入样例 #1

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

输出样例 #1

2 3

输入样例 #2

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

输出样例 #2

1 2

输入样例 #3

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

输出样例 #3

2 4