P1504 Block Castle

XC’s son, Xiao XC, loves building pretty castles with blocks. The castles are built from cubic blocks, and each layer of the castle is one block. Xiao XC is even smarter than his father, XC. He discovered that when building a castle, if the block below is larger than or equal to the block above, the castle is less likely to fall. So he always follows this rule when stacking. Xiao XC wants to give the castles he built to the pretty girls in his kindergarten to increase his popularity. To be fair, he decides to give each girl a castle of the same height, so the girls won’t argue over getting a prettier one. However, he realizes he didn’t plan for this in advance when building the castles. Since he has no extra blocks, he comes up with a clever plan: he will remove some blocks from each castle so that all castles end up with the same height. To make the castles as majestic as possible, he wants the final height to be as large as possible. Task: Please help Xiao XC write a program to decide which blocks to remove from each castle to achieve the best result. Note: The height of a castle is the sum of the edge lengths of all its blocks.

The first line contains an integer $n$, the number of castles. Each of the next $n$ lines contains a sequence of non-negative integers, separated by a space, giving the edge lengths of all blocks in one castle from bottom to top. The sequence ends with `-1`.

Output a single integer, the maximum possible final height of the castles. If no suitable plan exists, output $0$.

Constraints For $100\%$ of the testdata, $1 \le n \le 100$, each castle contains at most $100$ blocks, and each block’s edge length is at most $100$. Translated by ChatGPT 5