Preface

The following two problems, including this one, differ only in their constraints and time limits.

Coin Trade (Single)
Coin Trade (Multiple)

Problem Statement

yuki is planning a trip visiting country $1,$ country $2,\dots,$ country $N$ in this order.

The coin used in country $i$ is worth $A_i$ yen each. In addition, some countries have people interested in foreign coins, and you can exchange coins obtained in another country for coins of the country you are currently in.

In country $i$, you may choose zero or more of the following actions and perform them in any order.

• Choose $j > 0$. Pay $A_i \times j$ yen and obtain $j$ coins of country $i$.
• If you hold any of the $M_i$ kinds of coins of countries $B_{i1},B_{i2},\dots,B_{iM_i} \ (< i)$, you can exchange one such coin for one coin of country $i$.
  You may exchange multiple kinds of coins at the same time, but you cannot exchange two or more coins of the same kind for coins of country $i$. (Text corrected at 21:32)

However, since your wallet has limited capacity, you are not allowed to obtain coins in a way that would make the number of coins you hold exceed $K$ (yen is not counted).

Immediately after finishing the above actions each time, you may convert zero or more of the coins you hold into yen. A coin worth $A_i$ yen is converted into $A_i$ yen.

If you act optimally, how much can your yen increase between before the start of the trip and after the end of the trip? Find the maximum value.

You may assume that you have enough yen that it never runs out during the trip.

Input

$N\ K$
$A_1\ M_1$
$B_{11}\ B_{12} \dots B_{1M_1}$
$A_2\ M_2$
$B_{21}\ B_{22} \dots B_{2M_2}$
$\vdots$
$A_N\ M_N$
$B_{N1}\ B_{N2} \dots B_{NM_N}$

• All inputs are integers
• $1 \leq N \leq 5 \times 10^4$
• $1 \leq K \leq 50$
• $1 \leq A_i \leq 10^9$
• $0 \leq M_i < i$
• $\sum_{i=1}^{N} M_i \leq 5 \times 10^4$
• $1 \leq B_{i1} < B_{i2} < \dots < B_{iM_i} < i \ (1 \leq i \leq N)$

Output

Output the maximum value of the difference in yen between before the end of the trip and after the end of the trip when acting optimally.

Sample

2 1
3 0

5 1
1

2

3 2
1 0

2 1
1
3 1
1

3

15 3
2 0

1 0

14 1
2
20 1
1
11 1
3
1 0

10 0

7 1
1
17 1
6
4 1
6
11 0

20 5
3 5 6 10 11
4 2
6 11
1 1
13
7 3
4 8 11

96