前書き

本問を含む次の2問は、制約と実行時間制限のみが異なります。

Coin Trade (Single)
Coin Trade (Multiple)

問題文

yukiさんは国 $1,$ 国 $2,\dots,$ 国 $N$ をこの順に旅行する計画を立てています。

国 $i$ で使用されている硬貨の価値は、1枚あたり $A_i$ 円です。 さらにいくつかの国には他国の硬貨に興味のある人がおり、別の国で入手した硬貨と今いる国の硬貨を交換できます。

国 $i$ では、次の行動のうち0個以上を選んで任意の順に実行することができます。

• $j > 0$ を選ぶ。 $A_i \times j$ 円を払い、国 $i$ の硬貨 $j$ 枚を入手する。
• もし国 $B_{i1},B_{i2},\dots,B_{iM_i} \ (< i)$ の $M_i$ 種の硬貨のうちいずれかを所持しているならば、 その硬貨1枚と 国 $i$ の硬貨1枚とを交換できる。
  複数種類の硬貨を同時に交換できるが、同じ種類の硬貨2枚以上を国 $i$ の硬貨に交換することはできない。（21:32 文章を訂正）

しかし財布の容量には限界があるため、所持する硬貨が $K$ 枚を超えるような硬貨の入手は認められません（円は除く）。

上記の行動を終えた直後には毎回、所持している硬貨のうち0枚以上を円に換金することが可能です。 $A_i$ 円の価値の硬貨は $A_i$ 円に換金されます。

最適に行動した場合、旅行開始前と旅行終了後で円はいくら増えるでしょうか？その最大値を求めてください。

ただし円は十分多く持っているため途中で尽きることはないものとします。

入力

$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}$

• 入力は全て整数
• $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)$

出力

最適に行動した際の、旅行終了前と旅行終了後の円の差額の最大値を出力してください。

サンプル

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