410796: GYM104114 L Level Up

Steve discovered a new RPG video game he really wants to play. This game is unique: players who can finish it optimally get their money back for the game! What a world for Steve to live in!

The game has $$$n$$$ realms. The player starts in realm $$$1$$$, with level $$$1$$$ and a chosen quantity of hit points.

Each realm has a number of mobs, each with a specific strength. In each realm, the player should choose to engage and fight one non-empty subset of the mobs present in that realm. The fight happens in a turn-based combat system. First, all alive monsters attack, each of them yielding a damage to the player equal to its strength. Then, the player chooses one of the engaged mobs and kills it (that mob won't attack the player ever again). Every kill levels up the player (up to level $$$m$$$).

Once all the engaged mobs in realm $$$i$$$ are dead, the player heals $$$h_l$$$ hit points (where $$$l$$$ is its level after killing all the mobs) and advances to realm $$$i+1$$$. Advancing from realm $$$n$$$ will finish the game. There is no limit on the number of hit points the player can have in the play-through.

Steve's goal is to finish the game at the maximum level $$$m$$$ without ever having $$$0$$$ or less hit points on its play-through. Steve must play optimally, meaning that he needs to choose the minimum starting quantity of hit points possible such that he can finish the game with max-level.

The first line of the input contains two integers $$$n$$$ ($$$1 \leq n \leq 100$$$) and $$$m$$$ ($$$1 \leq m \leq 50\:000$$$)  — the number of realms, and the maximum level achievable in the game, respectively.

The second line of the input contains $$$m$$$ integers $$$h_1, h_2, \ldots, h_m$$$ ($$$1 \leq h_1 \leq h_2 \leq \ldots \leq h_m \leq 10^6$$$)  — the number of hit points the player gets healed, based on its level.

Finally, the next $$$n$$$ lines describe the $$$n$$$ realms. The $$$i$$$-th of these lines contains a number $$$k_i$$$ ($$$1 \leq k_i \leq 2000$$$) of mobs in realm $$$i$$$, followed by $$$k_i$$$ integers $$$s_{i, 1}, s_{i, 2}, \ldots, s_{i, k_i}$$$  — the strengths of each of the $$$k_i$$$ mobs.

All strengths are between $$$1$$$ and $$$10^4$$$ inclusively. Moreover, it is guaranteed that there are at least $$$m-1$$$ mobs in the entire game.

Output a single positive integer  — the minimum starting health possible.

3 4
1 2 10 11
3 6 2 3
2 11 12
4 9 11 10 5

9

Steve enters the first realm with $$$9$$$ HP. He engages the mobs with $$$2$$$ and $$$3$$$ strength. He starts the fight by taking $$$2 + 3 = 5$$$ damage, then kills the mob with $$$3$$$ strength, takes another $$$2$$$ damage, and kills the remaining mob. It gains level $$$3$$$ in the process, gets healed $$$h_3=10$$$ HP and advances with $$$12$$$ total HP.

In the second realm, Steve engages the mob with $$$11$$$ strength, takes $$$11$$$ damage, and kills it. He is now level $$$4$$$, therefore he gets healed $$$h_4=11$$$ HP and advances with $$$12$$$ total HP.

In the third realm, Steve engages one of the mobs (no matter which one), takes damage, kills it (without levelling up), and finishes the game at the maximum level $$$4$$$.