caminho pro iudex

#include <iostream>
using namespace std;

// Função para calcular a diversão na t-ésima corrida do brinquedo
int calculaDiversaoBrinquedo(int S, int B, int t) {
    return S - (t - 1) * (t - 1) * B;
}

// Função para calcular a diversão máxima possível com os créditos disponíveis
int calculaDiversaoMaxima(int S[], int B[], int C[], int N, int K) {
    int dp[25001] = {0}; // dp[x] armazena a diversão máxima possível com x créditos
    int new_dp[25001]; // Array auxiliar para atualizar os valores

    // Para cada brinquedo i
    for (int i = 0; i < N; i++) {
        // Copia os valores atuais de dp para new_dp
        for (int j = 0; j <= K; j++) {
            new_dp[j] = dp[j];
        }

        // Para cada corrida no brinquedo i
        for (int corrida = 1;; corrida++) {
            int diversaoAtual = calculaDiversaoBrinquedo(S[i], B[i], corrida); // Diversão da t-ésima corrida
            int custoAtual = C[i]; // Custo de uma única corrida

            // Se a diversão for menor ou igual a 0 ou o custo ultrapassar os créditos disponíveis, parar
            if (diversaoAtual <= 0 || custoAtual > K) {
                break;
            }

            // Atualiza a tabela dp de trás para frente (para garantir que cada combinação de corridas seja usada uma vez)
            for (int j = custoAtual; j <= K; j++) {
                new_dp[j] = max(new_dp[j], dp[j - custoAtual] + diversaoAtual);
            }
        }

        // Atualiza dp com os novos valores
        for (int j = 0; j <= K; j++) {
            dp[j] = new_dp[j];
        }
    }

    return dp[K]; // Retorna a diversão máxima possível com K créditos
}

int main() {
    int N; // Número de brinquedos
    cin >> N;

    int S[100], B[100], C[100]; // Arrays para armazenar diversão, aborrecimento e custo

    // Lendo as informações dos brinquedos
    for (int i = 0; i < N; i++) {
        cin >> S[i] >> B[i] >> C[i];
    }

    int V; // Número de visitas ao parque
    cin >> V;

    // Para cada visita, calcular a diversão máxima possível
    for (int j = 0; j < V; j++) {
        int K; // Créditos disponíveis na visita j
        cin >> K;

        // Calcula a diversão máxima possível com os créditos disponíveis na visita j
        int maxDiversao = calculaDiversaoMaxima(S, B, C, N, K);

        // Imprime o resultado da visita
        cout << j << ": " << maxDiversao << endl;
    }

    return 0;
}