時(shí)間限制 1000 ms
內(nèi)存限制 128 MB
題目描述
XC的兒子小XC最喜歡玩的游戲用積木壘漂亮的城堡。城堡是用一些立方體的積木壘成的括儒，城堡的每一層是一塊積木帮寻。小XC是一個(gè)比他爸爸XC還聰明的孩子固逗，他發(fā)現(xiàn)壘城堡的時(shí)候惜傲，如果下面的積木比上面的積木大盗誊，那么城堡便不容易倒隘弊。所以他在壘城堡的時(shí)候總是遵循這樣的規(guī)則开镣。
小XC想把自己壘的城堡送給幼兒園里漂亮的女孩子們，這樣可以增加他的好感度质欲。為了公平起見(jiàn)怎憋，他決定把送給每個(gè)女孩子一樣高的城堡盛霎，這樣可以避免女孩子們?yōu)榱双@得更漂亮的城堡而引起爭(zhēng)執(zhí)∑诰荆可是他發(fā)現(xiàn)自己在壘城堡的時(shí)候并沒(méi)有預(yù)先考慮到這一點(diǎn)。所以他現(xiàn)在要改造城堡缤苫。由于他沒(méi)有多余的積木了活玲，他靈機(jī)一動(dòng)，想出了一個(gè)巧妙的改造方案。他決定從每一個(gè)城堡中挪去一些積木，使得最終每座城堡都一樣高。為了使他的城堡更雄偉，他覺(jué)得應(yīng)該使最后的城堡都盡可能的高。
任務(wù)：
請(qǐng)你幫助小XC編一個(gè)程序，根據(jù)他壘的所有城堡的信息努酸，決定應(yīng)該移去哪些積木才能獲得最佳的效果获诈。
輸入數(shù)據(jù)
第一行是一個(gè)整數(shù) N (N≤ 100) 舔涎，表示一共有幾座城堡。以下 N 行每行是一系列非負(fù)整數(shù)，用一個(gè)空格分隔色瘩，按從下往上的順序依次給出一座城堡中所有積木的棱長(zhǎng)泥栖。用-1結(jié)束吧享。一座城堡中的積木不超過(guò)100塊钢颂，每塊積木的棱長(zhǎng)不超過(guò)100。
輸出數(shù)據(jù)
一個(gè)整數(shù)泵督，表示最后城堡的最大可能的高度救鲤。如果找不到合適的方案犹赖，則輸出 0 麸折。
樣例輸入
2
2 1 –1
3 2 1 –1
樣例輸出
3
