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){
			rrep(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<bits/stdc++.h>
using namespace std;
int dp[401][401][401]={};
int main(){
  int n;
  cin>>n;
  int s[401],l[401],p[401];
  
  for(int i=0;i<n;i++)
    cin>>s[i]>>l[i]>>p[i];
  
  for(int i=0;i<n;i++){
    for(int j=0;j<400;j++){
      for(int k=0;k<400;k++){
	int ny=min(s[i]+j,399);
	int nz=min(l[i]-s[i]+k,399);
	
	/*
	  if(i&&j-s[i-1]>=0&&k-(l[i-1]-s[i-1])>=0)
	  if(dp[i][j-s[i-1]][k-(l[i-1]-s[i-1])])
	    dp[i][j][k]=max(dp[i][j][k],dp[i][j-s[i-1]][k-(l[i-1]-s[i-1])]+p[i-1]);
	*/
	
	
	if(j+k==0){
	  dp[i+1][ny][nz]=max(dp[i+1][ny][nz],p[i]);
	  dp[i][ny][nz]=max(dp[i][ny][nz],dp[i][j][k]+p[i]);
	}
	dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]);
	
	if(dp[i][j][k]){
	  dp[i+1][ny][nz]=max(dp[i+1][ny][nz],dp[i][j][k]+p[i]);
	  dp[i][ny][nz]=max(dp[i][ny][nz],dp[i][j][k]+p[i]);
	}
      }
    }
  }
  int m,a[400],f=0;
  cin>>m;
  for(int i=0;i<m;i++){
    int w;
    cin>>w;
    int ans=0;
    for(int j=0;j<400;j++){
      for(int k=0;k<400;k++){
	if(j<=w&&j+k>=w)ans=max(ans,dp[n][j][k]);
      }
    }
    if(ans==0)f=1;
    a[i]=ans;
  }
  if(f)cout<<-1<<endl;
  else for(int i=0;i<m;i++)cout<<a[i]<<endl;
  return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
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; }
typedef long long ll;

const long long INF = 1LL << 60;

int main()
{
    int N;
    cin >> N;
    int s[N], l[N], p[N];
    rep(i, N) cin >> s[i] >> l[i] >> p[i];

    vector<vector<int>> dp(N+1, vector<int>(394, 0));

    rep(i, N) {
        rep(j, 394) {
            repd(k, s[i], l[i]+1) {
                
                if (j < k) chmax(dp[i+1][j], dp[i][j]);
                else chmax(dp[i+1][j], max(dp[i+1][j-k] + p[i], dp[i][j]));
                
            }
        }
    }

    int M;
    bool flag = true;
    cin >> M;

    int m[M];
    rep(i, M) cin >> m[i];

    rep(i, M) {
        if (dp[N][m[i]] == 0) {
            cout << -1 << endl;
            flag = false;
            break;
        }
    }

    if (flag) {
        rep(i, M) {
            cout << dp[N][m[i]] << endl;
        }
    }

    return 0;
}

C++: #include <algorithm>
#include <iostream>
#define N 393
using namespace std;
void func(int,int,int);
int n,s[N],l[N],p[N],m,w,a,ans[N],flag,flag2;
bool used[N];

int main(){
  cin>>n;
  for(int i=0;i<n;i++) cin>>s[i]>>l[i]>>p[i];
  cin>>m;
  for(int i=0;i<m;i++){
    cin>>w;
    a=-1;
    flag2=0;
    func(0,0,0);
    if(!flag2) a=-1;
    if(a==-1) flag=1;
    else ans[i]=a;
  }
  if(flag) cout<<-1<<endl;
  else{
    for(int i=0;i<m;i++) cout<<ans[i]<<endl;
  }
  return 0;
}

void func(int x,int len,int point){
  if(x==n){
    int suma=0,sumb=0;
    for(int i=0;i<n;i++)
      if(used[i]) suma+=s[i],sumb+=l[i];
    if(suma<=w&&w<=sumb) a=max(a,point);
    return ;
  }
  func(x+1,len,point);
  if(len+s[x]>w) return;
  flag2=1;
  used[x]=true;
  func(x+1,len+s[x],point+p[x]);
  used[x]=false;
}

C++: #include<bits/stdc++.h>

#define X first
#define Y second

#define reps(X,Y,Z) for(int X=Y; X <= Z; X++)
#define rep(X,Y) for(int (X)=0;(X) < (Y); ++(X))
#define rrep(X,Y) for(int (X)=(Y-1); X >= 0; ++(X))

#define all(X) (X).begin(),(X).end()


using namespace std;

int N,M,w;
int s[512];
int l[512];
int p[512];
int d[512];

int main(){
  cin >> N;
  rep(i,512)d[i] = -1;

  rep(i,N)
    cin >> s[i] >> l[i] >> p[i];

  d[0] = 0;
  rep(t,394){
    rep(i,N){
      reps(j,s[i],l[i]){
        int x = t + j;
        if(x > 393)break;
        if(d[t] == -1)continue; 
        d[x] = max(d[x], d[t]+p[i]);
      }
    }
  }
  cin >> M;

  vector<int> ans;
  rep(i,M){
    cin >> w;
    if(d[w] == -1){
      cout << "-1" << endl;
      return 0;
    }
    ans.push_back(d[w]);
  }
  rep(i,ans.size()){
    cout << ans[i]<< endl;
  }
  return 0;
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
  int n, m, s[393], l[393], p[393], w;
  vector< int > dp( 394, -1); //dp[i]:i長のメロディを作るための最大値
  dp[0] = 0;
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> s[i] >> l[i] >> p[i];
  }
  for(int i = 0; i < n; i++){
    for(int j = 393; j >= 0; j--){
      if(dp[j] == -1) continue;
      for(int k = s[i]; k <= l[i] && j + k < 394; k++){
        dp[j + k] = max( dp[j + k], dp[j] + p[i]);
      }
    }
  }
  cin >> m;
  while(m--){
    cin >> w;
    cout << dp[w] << endl;
  }
  return 0;
}