Proficient.
Put your skills to the test.

Problem summary

Choose at most one numbered ball from each of some ordered boxes. Read the chosen values in box order; they must be nondecreasing. Find their maximum possible total sum.

Constraints

1 ≤ n < 500; each box has 1–50 balls; each value is in 1…1000.

Worked example

Original statement sample.

10
3 2 2 4
2 1 2
3 3 7 10
4 5 5 1 1
1 3
1 2
3 1 9 1
1 5
7 8 1 1 1 1 2 1
1 3

25

Solution analysis

1. Let bestEnding[v] be the best sum of a valid selection from earlier boxes whose last value is exactly v. An empty selection has sum 0. For the next box, first compute prefix[v]=max(bestEnding[1…v]); this tells us the best selection to which a ball of value v may be appended.
2. A ball v can produce prefix[v]+v. Update bestEnding[v] with that candidate, leaving all other entries intact because skipping this box is allowed. Crucially, freeze the entire prefix array before processing this box: its updates must not help choose a second ball from the same box.
3. The sample selects values 2,2,3,5,5,8 from boxes 1,2,3,4,8,9, totaling 25. Equal adjacent selected values are permitted. For a single box containing 2 and 7, the answer is 7, not 9; the frozen prefix prevents taking both.
4. The value range is only 1000, so rebuilding prefix maxima once per box is simple and fast. No advanced data structure is needed. The largest sum is below 500·1000, comfortably inside int.

Why it works

Before each box, bestEnding represents exactly the optimal earlier selections by final value. Every legal selection using the box ends with one of its balls v and an earlier selection ending at most v, whose optimum is prefix[v]. Keeping both these candidates and all skip-box states therefore preserves the invariant. The final maximum over ending values is the desired optimum.

Watch out. Use ≤v when extending: the sequence is nondecreasing, not strictly increasing. Do not let updates from the current box enter its prefix array. Keep skip-box states instead of clearing bestEnding.

An independently written complete program with standard headers.

#include<algorithm>
#include<array>
#include<iostream>
using namespace std;
int main(){
    int boxes;
    cin>>boxes;
    const int maximumValue=1000;
    array<int,maximumValue+1>bestEnding{};
    array<int,maximumValue+1>prefix{};
    for(int box=0;box<boxes;box++){
        for(int value=1;value<=maximumValue;value++){
            prefix[value]=max(prefix[value-1],bestEnding[value]);
        }
        int count;
        cin>>count;
        for(int ball=0;ball<count;ball++){
            int value;
            cin>>value;
            // prefix is frozen, so this box cannot be used twice.
            bestEnding[value]=max(bestEnding[value],prefix[value]+value);
        }
    }
    cout<<*max_element(bestEnding.begin(),bestEnding.end())<<'\n';
}