Preface

The following 2 problems, including this one, differ only in their constraints and execution time limits. In particular, $K=1$ in this problem.

Coin Trade (Single)
Coin Trade (Multiple)

Problem Statement

Yuki is planning to travel through country $1,$ country $2,\dots,$ country $N$ in this order.

Each coin used in country $i$ is worth $A_i$ yen. Furthermore, in some countries there are people interested in foreign coins, and coins obtained in another country can be exchanged for coins of the current country.

In country $i$, Yuki can choose 0 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 Yuki holds any of the $M_i$ kinds of coins of countries $B_{i1},B_{i2},\dots,B_{iM_i} \ (< i)$, one such coin can be exchanged for one coin of country $i$.
  Multiple kinds of coins can be exchanged at the same time, but 2 or more coins of the same kind cannot be exchanged for coins of country $i$. (Text corrected at 21:32)

However, since the wallet has a limited capacity, obtaining coins such that the number of coins held exceeds $K$ is not allowed (yen is not counted).

Each time immediately after finishing the above actions, Yuki may convert 0 or more of the held coins into yen. A coin worth $A_i$ yen is converted into $A_i$ yen.

When acting optimally, how much does Yuki's yen increase between before the start of the trip and after the end of the trip? Find the maximum value.

Assume that Yuki has sufficiently many yen and will not run out along the way.

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 10^5$
• $K=1$
• $1 \leq A_i \leq 10^9$
• $0 \leq M_i < i$
• $\sum_{i=1}^{N} M_i \leq 10^5$
• $1 \leq B_{i1} < B_{i2} < \dots < B_{iM_i} < i \ (1 \leq i \leq N)$

Output

Output the maximum 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

2 1
2 0

1 1
1

0

15 1
13 0

3 1
1
16 0

7 0

12 1
4
14 1
1
10 1
2
1 1
1
16 2
1 6
5 2
2 5
13 1
8
2 3
2 6 8
4 2
3 7
10 1
5
13 3
1 4 9

19