최대 합

$n$개의 상자가 한 줄로 놓여 있다. 각 상자에는 여러 개의 공이 들어 있고, 각 공에는 정수 하나가 적혀 있다.

상자들 중 일부(하나, 여러 개, 또는 전부)를 고르고, 고른 각 상자에서 공을 정확히 하나씩 꺼내되 상자의 원래 순서는 유지한다. 꺼낸 공들을 그 순서대로 늘어놓으면 수열이 하나 만들어진다. 이 수열이 비내림차순(각 항이 이전 항보다 작지 않음)일 때에만 그 선택을 고려한다. 이러한 선택들 중에서 꺼낸 수들의 합이 최대가 되는 값을 구하시오.

첫째 줄에는 $n$이 주어진다. 이어지는 $n$개의 줄은 각각 하나의 상자를 나타내며, 그 상자에 들어 있는 공의 개수가 먼저 주어지고 그다음에 그 공들에 적힌 수들이 주어진다.

위에서 설명한 최대 합을 정수 하나로 출력한다.

$0 < n < 500$. 각 상자에는 공이 적어도 하나 있고 $50$개를 넘지 않는다. 공에 적힌 모든 수는 $1$ 이상 $1000$ 이하이다.