Go: ///
// File:  2502.go
// Author: ymiyamoto
//
// Created on Sat Mar 24 00:44:45 2018
//
package main

import (
	"fmt"
)

type phrase struct {
	s, l, p int
}

const melody_len int = 393

var n, m int

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func main() {
	fmt.Scan(&n)

	phrases := make([]phrase, n)
	max_count := 0
	for i := 0; i < n; i++ {
		fmt.Scan(&phrases[i].s, &phrases[i].l, &phrases[i].p)
		max_count += phrases[i].l
	}

	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, melody_len+1)
	}

	for i := range phrases {
		s := phrases[i].s
		l := phrases[i].l
		p := phrases[i].p
		for j := range dp[i] {
			for k := s; k <= l; k++ {
				if 0 <= j-k {
					dp[i+1][j] = max(dp[i+1][j], max(dp[i][j], dp[i+1][j-k]+p))
				} else {
					dp[i+1][j] = max(dp[i+1][j], dp[i][j])
				}
			}
		}
	}

	fmt.Scan(&m)
	var invalid bool
	var points []int
	for i := 0; i < m; i++ {
		var m int
		fmt.Scan(&m)
		if dp[n][m] == 0 {
			invalid = true
		}
		points = append(points, dp[n][m])
	}

	if invalid {
		fmt.Println(-1)
	} else {
		for _, p := range points {
			fmt.Println(p)
		}
	}
}

C++: // template {{{

#include <bits/stdc++.h>

// #define int long long

#define GET_MACRO(a, b, c, d, NAME, ...) NAME
#define REP2(i, n) REP3(i, 0, n)
#define REP3(i, a, b) REP4(i, a, b, 1)
#define REP4(i, a, b, s) for (int i = (a); i < (int)(b); i += s)
#define RREP2(i, n) RREP3(i, 0, n)
#define RREP3(i, a, b) for (int i = (b) - 1; i >= (int)(a); i--)

#define rep(...) GET_MACRO(__VA_ARGS__, REP4, REP3, REP2)(__VA_ARGS__)
#define rrep(...) GET_MACRO(__VA_ARGS__,, RREP3, RREP2)(__VA_ARGS__)
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define all(c) std::begin(c), std::end(c)
#define mp std::make_pair
#define mt std::make_tuple
#define fi first
#define se second
#define popcnt __builtin_popcountll

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vvi = std::vector<vi>;

template<typename T>
using maxpq = std::priority_queue<T, std::vector<T>, std::less<T>>;

template<typename T>
using minpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 10;
const ll LLINF = 1e18 + 10;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
const int dx8[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};

template<typename T>
inline T sq(T x){ return x * x; }

template<typename T, typename U>
inline bool chmax(T &x, U y){ if (x >= y) return false; x = y; return true; }

template<typename T, typename U>
inline bool chmin(T &x, U y){ if (x <= y) return false; x = y; return true; }

template<typename T>
inline void sort(T &c){ std::sort(std::begin(c), std::end(c)); }

template<typename T>
inline void reverse(T &c){ std::reverse(std::begin(c), std::end(c)); }

template<typename T>
inline void unique(T &c){ std::sort(std::begin(c), std::end(c)); c.erase(std::unique(all(c)), std::end(c)); }

using namespace std;

// }}}

int main()
{
	int dp[400];
	fill_n(dp, 400, -INF);
	dp[0] = 0;

	int n;
	cin >> n;
	rep(i, n){
		int a, b, c;
		cin >> a >> b >> c;
		rep(j, a, b + 1){
			rep(k, 400 - j){
				chmax(dp[k + j], dp[k] + c);
			}
		}
	}

	int m;
	cin >> m;
	rep(i, m){
		int w;
		cin >> w;
		cout << (dp[w] == -INF ? -1 : dp[w]) << endl;
	}
}

C++: #include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
const int LEN = 400;

int main() {
  int N; cin >>N;
  vector<int> v(LEN, -1);
  v[0] = 0;
  REP(z, N){
    int S, L, P; cin >>S >>L >>P;
    REP(i, LEN){
      if(v[i] == -1) continue;
      FOR(t, i + S, min(LEN, i + L + 1)) v[t] = max(v[t], v[i] + P);
    }
  }
  int M; cin >>M;
  vector<int> ws(M);
  bool f = 0;
  REP(i, M){
    int w; cin >>w;
    if(v[w] == -1) f = 1;
    ws[i] = w;
  }
  if(f) cout <<-1 <<endl;
  else REP(i, M) cout <<v[ws[i]] <<endl;
  return 0;
}

C++: /* ---------- STL Libraries ---------- */
// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

/* ---------- Namespace ---------- */
using namespace std;

/* ---------- Type Abbreviation ---------- */
using ll = long long;

/* ---------- Constants ---------- */
const ll MOD = 1e9 + 7;
// const int INF = 1 << 25;
// const ll INF = 1LL << 50;
// const double PI = acos(-1);
// const double EPS = 1e-10;
// mt19937 mert(LL(time(0)));

/* ---------- Short Functions ---------- */
template <typename T>
T gcd(T a, T b) {
    if (a > b) return gcd(b, a);
    return a == 0 ? b : gcd(b % a, a);
}

template <typename T, typename U>
T mypow(T b, U n) {
    if (n == 0) return 1;
    if (n == 1) return b /* % MOD */;
    if (n % 2 == 0) {
        return mypow(b * b /* % MOD */, n / 2);
    } else {
        return mypow(b, n - 1) * b /* % MOD */;
    }
}

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */

int main() {
    int n;
    cin >> n;

    int s[n];
    int l[n];
    int p[n];
    for (int i = 0; i < n; i++) {
        cin >> s[i] >> l[i] >> p[i];
    }

    int N = 0;
    for (int i = 0; i < n; i++) {
        N += l[i] - s[i] + 1;
    }

    int weights[N];
    int values[N];
    int pnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = s[i]; j <= l[i]; j++) {
            values[pnt] = p[i];
            weights[pnt++] = j;
        }
    }

    int M;
    cin >> M;

    int W[M];
    for (int m = 0; m < M; m++) {
        cin >> W[m];
    }

    int dp[400];
    fill(dp, dp + 400, 0);
    for (int i = 0; i < N; i++) {
        for (int j = weights[i]; j < 400; j++) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }

    int ret[M];
    fill(ret, ret + M, 0);

    for (int m = 0; m < M; m++) {
        if (dp[W[m]] == 0) {
            cout << -1 << endl;
            return 0;
        } else {
            ret[m] = dp[W[m]];
        }
    }

    for (int m = 0; m < M; m++) {
        cout << ret[m] << endl;
    }

    return 0;
}