B - Shopping List Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は大学生で、毎日の食事のために食材を買い出しに行きます。近所のスーパーマーケットでは N 種類の食材が販売されており、各食材には価格が設定されているほか、野菜か肉類のいずれか一方に分類されています。

高橋君は健康のため、毎回の買い物で野菜をちょうど 1 個、肉類をちょうど 1 個の、合計 2 個の食材を購入することにしています。

高橋君は M 日間の買い物計画を立てています。しかし、スーパーマーケットでは日によって品揃えが異なり、毎日すべての食材が購入できるわけではありません。

各食材 i（1 \leq i \leq N）について、価格 P_i と分類 T_i が与えられます。T_i = 0 なら食材 i は野菜、T_i = 1 なら食材 i は肉類です。各食材は野菜と肉類のいずれか一方にのみ属します。

また、各日 j（1 \leq j \leq M）について、その日に購入可能な食材の品目数 K_j と、購入可能な食材の番号のリスト S_{j,1}, S_{j,2}, \ldots, S_{j,K_j} が与えられます。同じ日の購入可能リストに同じ食材が重複して含まれることはありません。

各日について、その日に購入可能な食材の中から野菜を 1 個と肉類を 1 個選んだときの、価格の合計の最小値を求めてください。購入可能な食材の中に野菜と肉類の両方が含まれておらず、条件を満たす選び方が存在しない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq P_i \leq 10^9
  • T_i \in \{0, 1\}
  • 1 \leq K_j \leq N
  • 1 \leq S_{j,k} \leq N（1 \leq k \leq K_j）
  • 各日 j について、S_{j,1}, S_{j,2}, \ldots, S_{j,K_j} はすべて異なる
  • \sum_{j=1}^{M} K_j \leq 2 \times 10^5
  • 入力はすべて整数

入力

N M
P_1 T_1
P_2 T_2
\vdots
P_N T_N
K_1 S_{1,1} S_{1,2} ... S_{1,K_1}
K_2 S_{2,1} S_{2,2} ... S_{2,K_2}
\vdots
K_M S_{M,1} S_{M,2} ... S_{M,K_M}
  • 1 行目には、食材の種類数を表す整数 N と、買い物の日数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各食材の情報が与えられる。
  • 1 + i 行目には、食材 i の価格 P_i と、分類を表す値 T_i（0: 野菜、1: 肉類）が、スペース区切りで与えられる。
  • N + 2 行目から N + M + 1 行目では、各日に購入可能な食材の情報が与えられる。
  • N + 1 + j 行目には、j 日目に購入可能な食材の品目数 K_j と、購入可能な食材の番号 S_{j,1}, S_{j,2}, \ldots, S_{j,K_j} が、スペース区切りで与えられる。

出力

M 行出力してください。j 行目（1 \leq j \leq M）には、j 日目に購入可能な食材の中から野菜 1 個と肉類 1 個を選んだときの価格の合計の最小値を出力してください。条件を満たす選び方が存在しない場合は -1 を出力してください。

入力例 1

5 3
100 0
200 1
150 0
300 1
250 0
3 1 2 3
2 1 5
4 1 3 4 5

出力例 1

300
-1
400

入力例 2

6 4
500 0
300 1
200 0
400 1
150 0
600 1
3 1 3 5
2 2 4
5 1 2 3 4 5
2 1 3

出力例 2

-1
-1
450
-1

入力例 3

10 5
120 0
350 1
80 0
500 1
200 0
150 1
90 0
420 1
300 0
180 1
6 1 2 3 4 5 6
4 7 8 9 10
3 1 5 9
5 2 4 6 8 10
8 1 2 3 6 7 8 9 10

出力例 3

230
270
-1
-1
230

Score : 266 pts

Problem Statement

Takahashi is a university student who goes shopping for ingredients for his daily meals. A nearby supermarket sells N types of ingredients, each with a set price and classified as either a vegetable or meat.

For health reasons, Takahashi has decided to purchase exactly 1 vegetable and exactly 1 meat item, for a total of 2 ingredients, on each shopping trip.

Takahashi is planning his shopping over M days. However, the supermarket's stock varies by day, and not all ingredients are available for purchase every day.

For each ingredient i (1 \leq i \leq N), the price P_i and classification T_i are given. If T_i = 0, ingredient i is a vegetable; if T_i = 1, ingredient i is meat. Each ingredient belongs to exactly one of the two categories.

For each day j (1 \leq j \leq M), the number of available ingredients K_j and the list of available ingredient numbers S_{j,1}, S_{j,2}, \ldots, S_{j,K_j} are given. The same ingredient does not appear more than once in the available list for the same day.

For each day, find the minimum total price when selecting 1 vegetable and 1 meat item from the ingredients available on that day. If the available ingredients do not include both a vegetable and a meat item, making it impossible to satisfy the condition, output -1.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq P_i \leq 10^9
  • T_i \in \{0, 1\}
  • 1 \leq K_j \leq N
  • 1 \leq S_{j,k} \leq N (1 \leq k \leq K_j)
  • For each day j, S_{j,1}, S_{j,2}, \ldots, S_{j,K_j} are all distinct
  • \sum_{j=1}^{M} K_j \leq 2 \times 10^5
  • All input values are integers

Input

N M
P_1 T_1
P_2 T_2
\vdots
P_N T_N
K_1 S_{1,1} S_{1,2} ... S_{1,K_1}
K_2 S_{2,1} S_{2,2} ... S_{2,K_2}
\vdots
K_M S_{M,1} S_{M,2} ... S_{M,K_M}
  • The first line contains the integer N representing the number of ingredient types and the integer M representing the number of shopping days, separated by a space.
  • From the 2nd line to the (N + 1)-th line, information about each ingredient is given.
  • The (1 + i)-th line contains the price P_i of ingredient i and the classification value T_i (0: vegetable, 1: meat), separated by a space.
  • From the (N + 2)-th line to the (N + M + 1)-th line, information about the ingredients available on each day is given.
  • The (N + 1 + j)-th line contains the number of available ingredients K_j on day j and the available ingredient numbers S_{j,1}, S_{j,2}, \ldots, S_{j,K_j}, separated by spaces.

Output

Output M lines. On the j-th line (1 \leq j \leq M), output the minimum total price when selecting 1 vegetable and 1 meat item from the ingredients available on day j. If no valid selection exists, output -1.

Sample Input 1

5 3
100 0
200 1
150 0
300 1
250 0
3 1 2 3
2 1 5
4 1 3 4 5

Sample Output 1

300
-1
400

Sample Input 2

6 4
500 0
300 1
200 0
400 1
150 0
600 1
3 1 3 5
2 2 4
5 1 2 3 4 5
2 1 3

Sample Output 2

-1
-1
450
-1

Sample Input 3

10 5
120 0
350 1
80 0
500 1
200 0
150 1
90 0
420 1
300 0
180 1
6 1 2 3 4 5 6
4 7 8 9 10
3 1 5 9
5 2 4 6 8 10
8 1 2 3 6 7 8 9 10

Sample Output 3

230
270
-1
-1
230