The Most Valuable Tower

Jas has built several towers of different heights out of blocks. Each block has an integer written on it. A tower is more valuable the larger the sum of the blocks it contains. Jas wants to build the most valuable tower possible, but he does not want to completely destroy the towers he has already built. So he decided that the only move he may make is to choose two towers of different heights and:

• from the taller tower, remove exactly as many of its topmost blocks as there are blocks in the shorter tower (keeping their order) and form a new tower out of them;
• then place the other (shorter) tower, as a whole, on top of the tower from which the blocks were removed.

This produces two towers of the same heights as before, but possibly with a different arrangement of the numbers on the individual blocks (see the figure).

Figure: An example of Jas's move for the towers $(4, 5, 7, 1)$ and $(3, 6)$.

Find the maximum value of a tower that Jas can build.

The first line contains an integer $n$ ($1 \le n \le 500\,000$), the number of towers Jas built. Each of the next $n$ lines describes one tower. The $(i+1)$-th line contains an integer $w_i$ ($1 \le w_i \le 1\,000\,000$), the height of the $i$-th tower, followed by $w_i$ integers $x_1, x_2, \dots, x_{w_i}$ ($-1\,000\,000 \le x_k \le 1\,000\,000$), where $x_k$ is the number written on the $k$-th block from the top of the $i$-th tower. The total number of blocks $K$ across all towers does not exceed $1\,000\,000$.

Output a single integer: the maximum value of a tower that Jas can build.

Explanation: From towers no. 2 and no. 3 Jas can build the tower $(4, 6)$, and then from that tower together with tower no. 1 he can build the tower $(4, 6, 7, 1)$, whose value is $18$.