Kotlin Heroes: Episode 8 |
---|

Finished |

The following languages are only available languages for the problems from the contest

Kotlin Heroes: Episode 8:

- Kotlin 1.7.20
- Kotlin 1.9.21

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

*special problem

data structures

dp

*2500

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. A Battle Against a Dragon

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA squad of $$$n$$$ warriors is defending a castle from a dragon attack. There are $$$m$$$ barricades between the castle and the dragon.

The warriors are numbered from $$$1$$$ to $$$n$$$. The $$$i$$$-th warrior knows $$$k_i$$$ attacks: the $$$j$$$-th of them deals $$$a_{i,j}$$$ damage to the dragon and can only be applied if there are exactly $$$b_{i,j}$$$ barricades between the castle and the dragon.

The warriors make turns one after another, starting from warrior $$$1$$$. After warrior $$$n$$$ makes his turn, the total damage to the dragon is calculated. The $$$i$$$-th warrior performs exactly one of three possible moves in his turn:

- destroys one barricade (if there are any left);
- deploys one of his $$$k_i$$$ attacks;
- skips a turn.

The total damage is the sum of damages dealt by the warriors who chose to deploy their attacks in their turn. What is the maximum total damage the warriors can deal to the dragon?

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.

Examples

Input

2 4 1 2 4 2 10 5 3 4

Output

10

Input

3 3 1 1 0 1 20 2 1 100 3

Output

100

Input

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

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/19/2024 18:05:52 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|