# [Solution] A Battle Against a Dragon solution codeforces | Kotlin Heroes: Episode 8

## A Battle Against a Dragon solution codeforces

A squad of nn warriors is defending a castle from a dragon attack. There are mm barricades between the castle and the dragon.

The warriors are numbered from 11 to nn. The ii-th warrior knows kiki attacks: the jj-th of them deals ai,jai,j damage to the dragon and can only be applied if there are exactly bi,jbi,j barricades between the castle and the dragon.

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

1. destroys one barricade (if there are any left);
2. deploys one of his kiki attacks;
3. 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?

### A Battle Against a Dragon solution codeforces

Input

The first line contains two integers nn and mm (1n,m31051≤n,m≤3⋅105) — the number of warriors and the initial number of barricades.

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

The first line contains a single integer kiki (1kim+11≤ki≤m+1) — the number of attacks the ii-th warrior knows.

The second line contains kiki integers ai,1,ai,2,,ai,kiai,1,ai,2,…,ai,ki (1ai,j1091≤ai,j≤109) — the damage of each attack.

The third line contains kiki integers bi,1,bi,2,,bi,kibi,1,bi,2,…,bi,ki (0bi,jm0≤bi,j≤m) — the required number of barricades for each attack. bi,jbi,j for the ii-th warrior are pairwise distinct. The attacks are listed in the increasing order of the barricades requirement, so bi,1<bi,2<<bi,kibi,1<bi,2<⋯<bi,ki.

The sum of kiki over all warriors doesn’t exceed 31053⋅105.

### A Battle Against a Dragon solution codeforces

Output

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

### A Battle Against a Dragon solution codeforces

Examples
input

Copy
2 4
1
2
4
2
10 5
3 4

output

Copy
10

### A Battle Against a Dragon solution codeforces

input

Copy
3 3
1
1
0
1
20
2
1
100
3

output

Copy
100

### A Battle Against a Dragon solution codeforces

input

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

output

Copy
30

### A Battle Against a Dragon solution codeforces

Note

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

• warrior 11 destroys a barricade, now there are 33 barricades left;
• warrior 22 deploys his first attack (he can do it because b1,1=3b1,1=3, which is the current number of barricades).

The total damage is 1010.

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=72+5=7 or 55.

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 3030 total damage.