A Battle Against a Dragon

Description:

Input:

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$) — the number of warriors and the initial number of barricades.

Then the descriptions of attacks for each warrior follow. The $$$i$$$-th description consists of three lines.

The first line contains a single integer $$$k_i$$$ ($$$1 \le k_i \le m + 1$$$) — the number of attacks the $$$i$$$-th warrior knows.

The second line contains $$$k_i$$$ integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$$$ ($$$1 \le a_{i,j} \le 10^9$$$) — the damage of each attack.

The third line contains $$$k_i$$$ integers $$$b_{i,1}, b_{i,2}, \dots, b_{i,k_i}$$$ ($$$0 \le b_{i,j} \le m$$$) — the required number of barricades for each attack. $$$b_{i,j}$$$ for the $$$i$$$-th warrior are pairwise distinct. The attacks are listed in the increasing order of the barricades requirement, so $$$b_{i,1} < b_{i,2} < \dots < b_{i,k_i}$$$.

The sum of $$$k_i$$$ over all warriors doesn't exceed $$$3 \cdot 10^5$$$.

Output:

Print a single integer — the maximum total damage the warriors can deal to the dragon.

Sample Input:

2 4
1
2
4
2
10 5
3 4

Sample Output:

10

Sample Input:

3 3
1
1
0
1
20
2
1
100
3

Sample Output:

100

Sample Input:

2 1
2
10 10
0 1
2
30 20
0 1

Sample Output:

30

Note:

In the first example, the optimal choice is the following:

• warrior $$$1$$$ destroys a barricade, now there are $$$3$$$ barricades left;
• warrior $$$2$$$ deploys his first attack (he can do it because $$$b_{1,1}=3$$$, which is the current number of barricades).

The total damage is $$$10$$$.

If the first warrior used his attack or skipped his turn, then the second warrior would only be able to deploy his second attack. Thus, the total damage would be $$$2+5=7$$$ or $$$5$$$.

In the second example, the first warrior skips his move, the second warrior skips his move and the third warrior deploys his only attack.

In the third example, two equivalent options are:

• both warriors deploy their second attacks;
• the first warrior destroys one barricade and the second warrior deploys his first attack.

Both options yield $$$30$$$ total damage.