Level Up#12906

Level Up

2 seconds
256 megabytes
Very hard

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 realms. The player starts in realm , with level 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 ).

Once all the engaged mobs in realm are dead, the player heals h_l hit points (where is its level after killing all the mobs) and advances to realm i+1. Advancing from realm 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 without ever having 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.

Input

The first line of the input contains two integers (1 \leq n \leq 100) and (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 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 lines describe the realms. The -th of these lines contains a number k_i (1 \leq k_i \leq 2000) of mobs in realm , 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 and 10^4 inclusively. Moreover, it is guaranteed that there are at least m-1 mobs in the entire game.

Output

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

Examples

Example 1

Loading
Loading

Note

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

In the second realm, Steve engages the mob with strength, takes damage, and kills it. He is now level , therefore he gets healed h_4=11 HP and advances with 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 .