← 返回题目列表

Codeforces · 1185/F

F. 两个披萨

中文机器翻译题面 查看原题

一家由 $$$n$$$ 朋友组成的公司想要订购两份披萨。已知自然界中共有$$$9$$$种披萨原料,用$$$1$$$到$$$9$$$的整数表示。

每个 $$$n$$$ 朋友都有一种或多种最喜欢的食材:第 $$$i$$$ 位朋友最喜欢的食材数量等于 $$$f_i$$$ ($$$1 \le f_i \le 9$$$) 并且您最喜欢的食材形成序列 $$$b_{i1}, b_{i2}, \dots, b_{if_i}$$$ ($$$1 \le b_{it} \le 9$$$)。

CodePizza 餐厅的网站上正好有 $$$m$$$ ($$$m \ge 2$$$) 披萨。每个披萨的特点是包含一组 $$$r_j$$$ 成分 $$$a_{j1}, a_{j2}, \dots, a_{jr_j}$$$ ($$$1 \le r_j \le 9$$$, $$$1 \le a_{jt} \le 9$$$) ,其价格为 $$$c_j$$$。

帮助您的朋友恰好选择两个披萨,以满足公司最多人数的需求。众所周知,如果一个人所选择的披萨中至少含有他/她最喜欢的每种成分,那么他/她就会对这种选择感到满意。如果有多种方法可以选择两个披萨来满足最多数量的朋友,那么选择使两个披萨的总价格最小的一种。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^5, 2 \le m \le 10^5$$$) — 分别是公司中的朋友数量和披萨数量。

接下来,$$$n$$$ 行包含朋友最喜欢的食材的描述:其中第 $$$i$$$ 包含最喜欢的食材 $$$f_i$$$ 的数量 ($$$1 \le f_i \le 9$$$) 和一系列不同的整数 $$$b_{i1}, b_{i2}, \dots, b_{if_i}$$$ ($$$1 \le b_{it} \le 9$$$)。

接下来,$$$m$$$ 行包含披萨描述:其中第 $$$j$$$ 包含披萨 $$$c_j$$$ 的整数价格 ($$$1 \le c_j \le 10^9$$$)、成分数量 $$$r_j$$$ ($$$1 \le r_j \le 9$$$) 以及成分本身作为不同的序列整数 $$$a_{j1}, a_{j2}, \dots, a_{jr_j}$$$ ($$$1 \le a_{jt} \le 9$$$)。

输出

输出两个整数 $$$j_1$$$ 和 $$$j_2$$$ ($$$1 \le j_1,j_2 \le m$$$, $$$j_1 \ne j_2$$$) 表示所需集合中两个披萨的索引。如果有多个解,输出任意一个。披萨指数可以按任何顺序打印。

示例

输入 #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