long long solve(Group* groups) {

    long long* x = new long long[n + ];

    for (int i=; i<n+; i++) x[i] = INFINITY;

    x[] = ;

    // all groups but the last; the last always goes

    // into "last" bus

    for (int i=; i<m-; i++)

        for (int j=n-groups[i].size; j>=; j--) {

            long long time = max(x[j], groups[i].time);

            x[j+groups[i].size] = min(time, x[j+groups[i].size]);

        }

    //for (int i=0; i<=n; i++) cout << x[i] << " ";

    //cout << endl;

    long long answer = -;

    for (int i=; i<=k; i++)

        if (n - i <= k) if (x[i] < INFINITY) {

            long long total = x[i] * i + (n - i) * groups[m-].time;

            if (answer == - || total < answer)

                answer = total;

        }

    return answer;

}