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++: #include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

class dp{
public:
  int n;
  static const int wlimit=393;
  int *s, *l, *p;
  int (*d)[wlimit+1];
  bool (*can)[wlimit+1];
  dp(int n):n(n){
    s = new int[n+1];
    l = new int[n+1];
    p = new int[n+1];
    d = new int[n+1][wlimit+1];
    can = new bool[n+1][wlimit+1];
  }
  ~dp(){
    delete[] s;
    delete[] l;
    delete[] p;
    delete[] d;
  }

  void init(){
    for(int i=0; i<=n; i++){
      for(int j=0; j<=wlimit; j++) {
        d[i][j] = 0;
        if(j==0) can[i][j] = true;
        else can[i][j] = false;
      }
    }
    for(int i=1; i<=n; i++){
      for(int j=0; j<=wlimit; j++){
        int temp=0;
        for(int k=s[i]; k<=l[i]; k++){
          if(j<k) temp = max(temp, d[i-1][j]);
          else {
            if(can[i][j-k]){
              temp = max(temp, max(d[i-1][j], d[i][j-k]+p[i]));
              can[i][j] = true;
            }
          }
        }
        d[i][j] = temp;
      }
    }
  }

  vector<int> ans(vector<int> w){
    vector<int> ans;
    for(int i=0; i<w.size(); i++){
      if(d[n][w[i]]==0){
        ans = vector<int>(1, -1);
        return ans;
      }
      ans.push_back(d[n][w[i]]);
    }
    return ans;
  }
};

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

  int s, l, p;
  for(int i=1; i<=n; i++){
    cin >> s >> l >> p;
    d.s[i] = s;
    d.l[i] = l;
    d.p[i] = p;
  }

  d.init();

  int m; cin >> m;
  vector<int> melodies;
  for(int i=0; i<m; i++){
    int w; cin >> w;
    melodies.push_back(w);
  }

  vector<int> ans = d.ans(melodies);
  for(int i=0; i<ans.size(); i++){
    cout << ans[i] << endl;
  }

  return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<cmath>
#include<iomanip>
#include<functional>
using namespace std;

int MOD = 1e9 + 7;

typedef long long ll;
typedef pair<int, int> P;

int main() {
	int n;
	cin >> n;
	vector<int> s(n + 1), l(n + 1), p(n + 1);
	for (int i = 1; i <= n; i++) cin >> s[i] >> l[i] >> p[i];
	int m;
	cin >> m;
	vector<int> w(m + 1);
	for (int i = 1; i <= m; i++) cin >> w[i];

	vector<vector<int>> dp(400, vector<int>(400, 0));
	vector<int> ans(m + 1);

	for (int k = 1; k <= m; k++) {
		int MAX = 0;

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= w[k]; j++) {

				if (j >= s[i]) {
					dp[i][j] = max(dp[i - 1][j], dp[i][j - s[i]] + p[i]);
				}
				else {
					dp[i][j] = dp[i - 1][j];
				}
			}
		}

		for (int i = 1; i <= w[k]; i++) {
			MAX = max(MAX, dp[n][i]);
		}

		if (MAX == 0) {
			cout << -1 << endl;
			return 0;
		}

		ans[k] = MAX;
	}

	for (int i = 1; i <= m; i++) {
		cout << ans[i] << endl;
	}
}

C++: //#include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <cmath>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <numeric>
//#include <windows.h>
using namespace std;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
template<class T> using VVV = V<VV<T>>;
template<class T> using G = greater<T>;
template<class T1, class T2> using P = pair<T1, T2>;
using I = int;
using D = double;
using B = bool;
using C = char;
using S = string;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = P<I, I>;
using VPII = V<PII>;
using PLL = P<LL, LL>;
using VPLL = V<PLL>;
using VI = V<I>;
using VVI = VV<I>;
using VLL = V<LL>;
using VVLL = VV<LL>;
using VC = V<C>;
using VVC = VV<C>;
using VS = V<S>;
using VVS = VV<S>;
using VB = V<B>;
using VVB = VV<B>;
#define REP(type, i, n) for (type i = 0; i < (type)(n); ++i)
#define REP2(type, i, m, n) for (type i = (m); i < (type)(n); ++i)
#define REPR(type, i, n) for (type i = (n)-1; i >= 0; --i)
#define REPR2(type, i, m, n) for (type i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a, type) sort(ALL(a), G<type>())
#define REVERSE(a) reverse(ALL(a))
#define SIZE(a, type) ((type)(a).size())
#define bit_search(bit, n) REP(LL, bit, 1LL<<(n))
#define bit_check(bit, i) ((bit>>(i)) & 1)
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) lower_bound(ALL(a), (x)) - a.begin()
#define bisect_right(a, x) upper_bound(ALL(a), (x)) - a.begin()
#define INPUT(a) REPx(&x, a) cin >> x;
#define INPUTP(a) REPx(&x, a) cin >> x.first >> x.second;
#define OUTPUT_PERMUTATION(n) do{VI v(n); iota(ALL(v), 1); do{REPx(x, v) cout << x << " "; ENDL} while(next_permutation(ALL(v)));} while(0);
#define MAKE_PERMUTATION(n, PER) do{VVI a(fact(n), VI(n)); int idx = 0; VI v(n); iota(ALL(v), 1); do{REP(roop, n) a[idx][roop] = v[roop]; idx++;} while(next_permutation(ALL(v))); PER = a;} while(0); // int fact(), VVI PERを宣言しておく、n=10が限界(500 ms)
#define ENDL cout << endl;

template<class T> using PRIORITY_QUEUE = priority_queue< T, V<T>, G<T> >;

template<class T> inline bool chmin(T &a, T b){if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){if (a < b) {a = b; return true;} return false;}

const int INF = 2e9;
const LL MOD = 1e9 + 7;

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n;
  VI P(394, 0);
  REP(int, i, n)
  {
    int s, l, p;
    cin >> s >> l >> p;
    REP2(int, i, s, l+1) chmax(P[i], p);
  }
  cin >> m;
  VI ans(m);
  REP(int, roop, m)
  {
    int w;
    cin >> w;
    VVI dp(394, VI(w+1, 0));
    REP(int, i, 393) REP(int, j, w+1)
    {
      dp[i+1][j] = dp[i][j];
      if (j-i >= 0) chmax(dp[i+1][j], dp[i+1][j-i] + P[i]);
    }
    int res = dp[393][w] ? dp[393][w] : -1;
    if (res == -1)
    {
      cout << -1 << endl;
      return 0;
    }
    ans[roop] = res;
  }
  REP(int, i, m) cout << ans[i] << endl;

  return 0;
}

C++: #include<iostream>
#include<vector>

using namespace std;

struct MEL{int s,l,p;};
const int MAX = 400;
int dp[MAX];
vector<MEL> V;

void solve(){

  fill(dp,dp+MAX,-1);

  dp[0] = 0;
  for(int i = 0; i < V.size(); i++)
    for(int j = V[i].s; j <= V[i].l; j++)
      for(int k = 0; k < MAX && k+j < MAX; k++)
	if(dp[k] >= 0) dp[k+j] = max(dp[k+j],dp[k]+V[i].p); 
      

  vector<int> ans;
  int m;
  cin >> m;
  while(m--){
    int in;
    cin >> in;
    if(dp[in] == -1){
      cout << "-1" << endl;
      return;
    }
    ans.push_back(dp[in]);
  }
  for(int i = 0; i < ans.size(); i++)
    cout << ans[i] << endl;
}

int main(){

  int n;
  cin >> n;
  while(n--){
    MEL mel;
    cin >> mel.s >> mel.l >> mel.p;
    V.push_back(mel);
  }
  solve();
  return 0;
}