A Battle Against a Dragon
Contest: Kotlin Heroes: Episode 8
Difficulty rating: 2500
Tags: *special, data structures, dp

A 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:

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

Input format:
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 format:
Print a single integer — the maximum total damage the warriors can deal to the dragon.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

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.

Example input:
2 4
1
2
4
2
10 5
3 4

Example output:
10

Example input:
3 3
1
1
0
1
20
2
1
100
3

Example output:
100

Editorial:
Obviously, the problem requires some sort of dynamic programming.
Consider the simplest one. $$$dp_{i,j}$$$ is the maximum total damage dealt by the first $$$i$$$ warriors if there are $$$j$$$ barricades after the move of the $$$i$$$-th warrior. The transitions are exactly the same as they are written in the statement.
That solution works in $$$O(nm)$$$ which is too slow. Let's analyze the behavior of the transitions on the dp table. The transition that destroys a barricade moves the value in some cell $$$(i,j)$$$ to $$$(i+1,j-1)$$$. The transition, that does nothing, moves it to $$$(i+1,j)$$$. The important thing to notice is that only the attack transition changes the value before updating the other state.
Thus, the idea is to write the dp in such a way that useless states produced by the first two transitions aren't stored explicitly and only collected by the attack transitions.
Let's restate the dp. $$$dp_{i,k}$$$ is the total damage dealt by the first $$$i$$$ warriors if the $$$i$$$-th warrior used his $$$k$$$-th attack. Notice that the fact that the attack was possible helps to identify the current number of barricades. To update such a dp we should iterate over both the previous warrior to attack and the attack he used.
Let the previous warrior be $$$j (j < i)$$$, his attack was when there were $$$x$$$ barricades and the attack of the $$$i$$$-th warrior was when there were $$$y$$$ barricades. If $$$x < y$$$, then there was no way for the $$$i$$$-th warrior to use his attack. At the same time, if $$$x - y \ge i - j$$$, then the warriors between the $$$j$$$-th and the $$$i$$$-th one have no way to destroy enough barricades. Otherwise, there is a way to assign either of the two moves to them in such a way that exactly $$$y$$$ barricades are left. Thus, $$$y \le x \le (i - j) + y$$$ should hold for the transition to be possible.
Picture a set of possible states, which can update $$$dp_{i,k}$$$, on the table. It looks like a triangle starting from $$$(i-1,y)$$$ and going vertically to the top and diagonally to the top-right.
That screams data structures, and we are finally approaching them.
I propose the following way to calculate the dp. Sort the attacks of all warriors altogether, first, in the decreasing order of the number of barricades and, second, in the increasing order of the warrior index.
Store a BIT such that its $$$i$$$-th position contains the maximum value of dp over the $$$i$$$-th diagonal (going from top-right to bottom-left). Now you can forget that the query area is a triangle and query on the entire prefix of the diagonals. The values in the required area are calculated already, and the values outside of it that get captured by the query are not calculated yet (due to being to the left of the triangle).
The answer is the maximum value stored in the entire BIT at the end.
Overall complexity: $$$O((\sum \limits_{i=1}^n k_i) \cdot \log(n + m))$$$.