Maximal Equal Castle Height

Little XC loves to build castles using cubic blocks. Each castle is built by stacking blocks, one per level, from bottom to top. In his building process, he always places a larger block beneath a smaller one to ensure stability. The height of a castle is defined as the sum of the edge lengths of its blocks.

After building several castles, little XC decides to gift them to the girls at his kindergarten. To be fair, he wants to give each girl a castle of the same height. However, he cannot add any more blocks and his only option is to remove some blocks from each castle. When removing blocks, he can only remove blocks from the top of a castle. That is, from each castle you are allowed to choose a prefix (the bottom part) of the castle, so that the height (the sum of the chosen blocks) is reduced.

Your task is to help little XC determine the maximum possible height \(H\) such that each castle can be reduced (by removing some blocks from the top) to exactly height \(H\). If no positive common height exists, output 0.

The height of a castle with blocks of edge lengths \(a_1, a_2, \dots, a_m\) (from bottom to top) is computed as: \[ H_k = \sum_{j=1}^{k} a_j, \quad k = 1,2,\dots, m. \]

inputFormat

The first line contains a single integer \(n\) (\(1 \leq n \leq 10^5\)) representing the number of castles.

Each of the following \(n\) lines describes one castle. Each line begins with an integer \(m\) (\(1 \leq m \leq 10^5\)), the number of blocks in the castle, followed by \(m\) positive integers representing the edge lengths of the blocks from bottom to top. It is guaranteed that for each castle, the blocks are arranged so that the block at the bottom is strictly larger than the one above it.

Note: The overall sum of all \(m\) values does not exceed \(10^6\).

outputFormat

Output a single integer, the maximum height that can be achieved by all castles after removing some (possibly zero) blocks from the top of each castle. If it is impossible to obtain a common positive height, output 0.

sample

3
3 4 3 2
4 6 1 3 2
3 2 5 2

7