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>
using namespace std;
typedef long long ll;
ll n, s[400], l[400], p[400], dp[400], m, w[400];
const ll INF = -1000000000000000000;
int main(void){
    // Your code here!
    cin >> n;
    for (ll i = 0; i < n; i++) cin >> s[i] >> l[i] >> p[i];
    for (ll i = 1; i <= 393; i++) dp[i] = INF;
    for (ll i = 1; i <= 393; i++) {
        for (ll j = 0; j < n; j++) {
            for (ll k = s[j]; k <= l[j]; k++) {
                if (k > i || dp[i - k] == INF) continue;
                dp[i] = max(dp[i], dp[i - k] + p[j]);
            }
        }
    }
    cin >> m;
    for (ll i = 0; i < m; i++) {
        cin >> w[i];
        if (dp[w[i]] == INF) {
            cout << -1 << endl;
            return 0;
        }
    }
    for (ll i = 0; i < m; i++) {
        cout << dp[w[i]] << endl;
    }
}

C++: #include<iostream>
#include<set>
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

class Phrase {
    public:
    int s,l,p;
    Phrase(int s,int l,int p) {

        this->s = s;
        this->l = l;
        this->p = p;
    }
    Phrase() {
        s=l=p=0;
    }

};

int n;
Phrase phra[400];
int m;
int w[400];
int dp[400];

int main() {

    cin>>n;
    rep(i,n) {
        int s,l,p;
        cin>>s>>l>>p;
        phra[i] = Phrase(s,l,p);
    }
    cin>>m;
    rep(i,m) cin>>w[i];
    rep(i,400) dp[i]=-1000000;
    dp[0]=0;

    rep(i,n) {
        for(int j=phra[i].s;j<=phra[i].l;j++) {
            for(int k=0;k<400;k+=j) {
                dp[k+j] = max(dp[k+j],dp[k]+phra[i].p);
            }
        }
    }

    multiset<int> ans;
    bool flag = false;
    
    rep(i,m) {
        int t = dp[w[i]];
        if(t < 0) flag=true;
        ans.insert(dp[w[i]]);
    }
    if(flag || ans.find(-1) != ans.end()) {
        cout<<"-1"<<endl;
        return 0;
    }

    multiset<int>::iterator it = ans.begin();
    while(it != ans.end()) {
        cout<<(*it)<<endl;
        it++;
    }

    return 0;
}

C++: 
#include<iostream>
using namespace std;

#define N 400
#define W 400

#define max(a,b) (a>b?a:b)

int main() {
  int n, m, s[N], l[N], p[N];
  int dp[N+1][W+1], w[N];
  bool f = false;
  cin >> n;
  for(int i=0; i<n; ++i) cin >> s[i] >> l[i] >> p[i];
  for(int i=0; i<=n; ++i) dp[i][0] = 0;
  for(int i=0; i<=W; ++i) dp[0][i] = 0;
  for(int i=0; i<n; ++i) {
    for(int j=1; j<=W; ++j) {
      dp[i+1][j] = dp[i][j];
      for(int t=s[i]; t<=l[i]; ++t) {
        if(j-t<0) break;
        dp[i+1][j] = max(dp[i+1][j], dp[i+1][j-t] + p[i]);
      }
    }
  }
  cin >> m;
  for(int i=0; i<m; ++i) {
    cin >> w[i];
    if(dp[n][w[i]]==0) f = true;
  }
  if(f) cout << "-1" << endl;
  else for(int i=0; i<m; ++i) {
      cout << dp[n][w[i]] << endl;
    }
  return 0;
}

C++: #include<iostream>
#include<vector>
using namespace std;
static const int MAX = 500;

int n;
int s[MAX], l[MAX], p[MAX];

void solve(int dp[]){
  for ( int i = 0; i <= MAX; i++ ) dp[i] = -1;
  dp[0] = 0;
  for ( int i = 0; i <= MAX; i++ ){
    if ( dp[i] == -1 ) continue;
    for ( int k = 0; k < n; k++ ){
      for ( int j = i+s[k]; j <= i+l[k]; j++ ){
	if ( j > MAX ) continue;
	dp[j] = max(dp[j], dp[i] + p[k]);
      }
    }
  }
}

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

  solve(dp);

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

C++: #include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))

using P = pair<int, int>;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector< P > wv;
    int l, r;
    int p;
    rep (i, n)
    {
        cin >> l >> r >> p;
        for (int j = l; j <= r; ++j)
        {
            wv.emplace_back(j, p);
        }
    }

    vs32 dp(394, 0);
    rep (i, wv.size())
    {
        for (int j = wv[i].first; j <= 393; ++j)
        {
            dp[j] = MAX(dp[j], dp[j - wv[i].first] + wv[i].second);
        }
    }

    int m;
    cin >> m;
    vs32 w(m);
    rep (i, m)
    {
        cin >> w[i];
        if (dp[w[i]] == 0)
        {
            cout << "-1\n";
            return 0;
        }
    }

    rep (i, m)
    {
        cout << dp[w[i]] << "\n";
    }

    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define MAX_N 400
#define MAX_L 400

int dp[MAX_N][MAX_L];

int main() {
    int n,s,l,p,mn,w;
    map<int,int> m;
    vector<int> a,b;
    cin >> n;

    rep(i,n) {
        cin >> s >> l >> p;
        rep(j,l-s+1) {
            if(!m.count(j+s))
                m[j+s] = p;
            else
                m.at(j+s) = max(m.at(j+s), p);
        }
    }

    for(auto p : m) {
        a.push_back(p.first);
        b.push_back(p.second);
    }

    rep(i,MAX_N)
        rep(j,MAX_L)
            dp[i][j] = 0;

    rep(i,a.size())
        rep(j,MAX_L) {
            if(a.at(i) > j)
                dp[i+1][j] = dp[i][j];
            else
                dp[i+1][j] = max(dp[i][j], dp[i+1][j-a.at(i)]+b.at(i));
        }
    
    cin >> mn;
    vector<int> r(mn);
    rep(i,mn) {
        cin >> w;
        if(dp[a.size()][w] == 0) {
            cout << -1 << endl;
            return 0;
        }
        r.at(i) = dp[a.size()][w];
    }

    rep(i,mn)
        cout << r.at(i) << endl;
}