Problem Statement

At Yuyu's school, the final exams are coming up tomorrow.
There are as many as $N$ subjects on the exams, but Yuyu has not started studying yet.
The following holds regarding Yuyu's studying and exam scores. Note that exams at Yuyu's school have no maximum score, and the subjects are numbered from $1$ to $N$.

• For $i=1,\dots,N$, studying subject $i$ allows Yuyu to score $M$ points in subject $i$.
• Studying subject $i$ makes it easier to gain a deep understanding of $k_i$ subjects $A_{ij}\ (1\leq j \leq k_i)$.
  As a result, if both subject $i$ and subject $A_{ij}$ are studied, the score in subject $A_{ij}$ increases by $B_{ij}$ points.
• Studying is tiring, so if Yuyu studies subject $i$, Yuyu must replenish $C_i$ units of the mofumofu component.

Now, Yuyu wants to get good results on the exams, but would hate to waste by replenishing too much of the mofumofu component.
By appropriately choosing the subjects to study, maximize the value of (the sum of the exam scores) $-$ (the amount of the mofumofu component replenished).

Input

$N\ M$
$\mathrm{Info}_1$
$\vdots$
$\mathrm{Info}_N$

Here, each $\mathrm{Info}_i$ is given in the following format. Note that when $k_i=0$, $\mathrm{Info}_i$ consists of only $1$ line.

$k_i\ C_i$
$A_{i1}\ \cdots\ A_{ik_{i}}$
$B_{i1}\ \cdots\ B_{ik_{i}}$

• $1 \leq N \leq 100$
• $0 \leq M \leq 10^9$
• $0 \leq k_i \leq N-1\ (1 \leq i \leq N)$
• $1 \leq A_{ij} \leq N,\ A_{ij} \neq i\ (1\leq i \leq N,\ 1 \leq j \leq k_i)$
• $A_{ij} \lt A_{i(j+1)}\ (1\leq i \leq N,\ 1 \leq j \lt k_i)$
• $0 \leq B_{ij},\,C_i \leq 10^9\ (1 \leq i \leq N,\,1 \leq j \leq k_i)$
• All input values are integers.

Output

Output the maximum value of (the sum of the exam scores) $-$ (the amount of the mofumofu component replenished) that Yuyu can obtain by appropriately choosing the subjects to study.

Print a newline at the end.

Sample

3 100
1 50
2
15
1 200
3
5
2 20
1 2
20 10

150

3 100
1 1000000000
2
15
1 1000000000
3
5
2 1000000000
1 2
20 10

0

3 0
0 5
0 5
0 5

0

5 457570553
2 935681835
3 5
646317136 229179330
1 732053682
5
460010336
3 219961142
2 4 5
805316947 35611550 19086292
2 80909206
3 5
896187710 518478057
2 391491330
3 4
767870553 307252308

4613065789