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)
		}
	}
}

Python: import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

n = INT()
slp = [LIST() for _ in range(n)]
m = INT()
w = [INT() for _ in range(m)]

dp = [0]*394

v = [0]*394
for s, l, p in slp:
	for x in range(s, l+1):
		v[x] = max(v[x], p)


for i in range(394):
	for j in range(i+1):
		dp[i] = max(dp[i], dp[i-j]+v[j])

ans = []
for i in w:
	if dp[i] == 0:
		print(-1)
		break
	else:
		ans.append(dp[i])
else:
	print(*ans, sep="\n")

C++: #include<iostream>
#include<algorithm>
using namespace std;
int dp[1000];
int l[1000], r[1000], m[1000];
int N, Q;
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> l[i] >> r[i] >> m[i];
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 400; j++) {
			for (int k = l[i]; k <= r[i]; k++) {
				dp[j + k] = max(dp[j + k], dp[j] + m[i]);
			}
		}
	}
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		int a; cin >> a;
		if (dp[a] == 0) { cout << "-1" << endl; }
		else { cout << dp[a] << endl; }
	}
	return 0;
}

C++: #include <iostream>
using namespace std;
typedef long long ll;
ll n,m,a,b,c,dp[394],ch[393],A[393];
int main(void){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a>>b>>c;
        a--,b--;
        for(int i=a;i<=b;i++){
            ch[i]=max(ch[i],c);
        }
    }
    for(int i=0;i<393;i++){
        for(int j=393;j>=0;j--){
            for(int k=1;k<=393;k++){
                if(j==0||dp[j]>0){
                    if(j+k*(i+1)<=393){
                        dp[j+k*(i+1)]=max(dp[j+k*(i+1)],dp[j]+ch[i]*k);
                    }
                    else break;
                }
            }
        }
    }
    cin>>m;
    for(int i=0;i<m;i++){
        cin>>a;
        if(dp[a]==0){
            cout<<-1<<endl;
            return 0;
        }
        A[i]=dp[a];
    }
    for(int i=0;i<m;i++){
        cout<<A[i]<<endl;
    }
    //for(int i=0;i<15;i++)cout<<dp[i]<<endl;
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int> P;
int main(){
  int n;
  cin>>n;
  vector<int> p(n);
  vector<P> mk(n);
  for(int i=0;i<n;i++){
    cin>>mk[i].first>>mk[i].second>>p[i];
  }
  int m;
  cin>>m;
  vector<int> w(m);
  rep(i,m)
    cin>>w[i];
  vector<int> dp(400,-1);
  dp[0]=0;
  rep(i,400){
    rep(j,n){
      for(int k=mk[j].first;k<=mk[j].second;k++){
	if(i-k>=0&&dp[i-k]!=-1){
	  dp[i]=max(dp[i],dp[i-k]+p[j]);
	}
      }

    }

  }
  /*rep(i,100)
    cout<<dp[i]<<" "<<i<<endl;
  */
  vector<int> ans(m);
  rep(i,m){
    ans[i]=dp[w[i]];
    if(ans[i]==-1){
      cout<<"-1"<<endl;
      return 0;
    }
  }
  rep(i,m){
    cout<<ans[i]<<endl;
  }

  return 0;
}

C++: #include <stdio.h>
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define MAX (400)

using namespace std;

typedef long long ll;

int n, m, s[MAX], l[MAX], p[MAX], w[MAX];
int dp[MAX];

int main() {
    /* 入力 */
    cin >> n;
    REP(i, n) {
        cin >> s[i] >> l[i] >> p[i];
    }
    
    cin >> m;
    REP(i, m) {
        cin >> w[i];
    }
    
    fill(dp, dp + MAX, -1);
    dp[0] = 0;
    
    /* メロディの長さの最大点数を作って行く */
    REP(i, MAX) {
        REP(j, n) {
            FOR(k, s[j], l[j] + 1) {
                if (i - k >= 0) {
                    dp[i] = max(dp[i], dp[i - k] + p[j]);
                }
            }
        }
    }
    
    /* 初期値のままだったら-1 */
    REP(i, m) {
        if (dp[w[i]] < 0) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    /* 答えの出力 */
    REP(i, m) {
        cout << dp[w[i]] << endl;
    }
    
    return 0;
}

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

const int len = 393;
int main(){
  int n;
  cin >> n;
  vector<int> dp(len+1,-1);
  dp[0] = 0;

  rep(i,n){
    int s,l,p;
    cin >> s >> l >> p;
    rep(j,len+1){
      if(dp[j]<0)continue;
      for(int t=s;t<=l;t++){
	if(j+t<=len){
	  dp[j+t] = max(dp[j+t], dp[j] + p);
	}
      }
    }
  }

  int m;
  cin >> m;
  vector<int> ans(m);
  rep(i,m){
    int w;
    cin >> w;
    if(dp[w]<0){
      cout << -1 << endl;
      return 0;
    }
    ans[i] = dp[w];
  }
  rep(i,m)cout << ans[i] << endl;
}

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

using namespace std;

int main(void){
int n,m,s[400],l[400],p[400],w[400],dp[400];

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[i];

fill(dp,dp+400,-1);
dp[0]=0;

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

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


for(int i=0;i<m;i++){
cout << dp[w[i]] << endl;
}

return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int dp[999],a[999],l[999],r[999],m[999],N,Q,i,j,k,OK;
main(){
	cin>>N;
	for(i=0;i<N;i++)cin>>l[i]>>r[i]>>m[i];
	for(i=0;i<N;i++)
		for(j=0;j<400;j++)
			for(k=l[i];k<=r[i];k++)
				dp[j+k]=max(dp[j+k],dp[j]+m[i]);
	cin>>Q;
	for(i=0;i<Q;i++){
		cin>>a[i]; 
		OK=dp[a[i]]?OK:1;
	}
	if(OK)cout<<"-1\n";
	else for(i=0;i<Q;i++)cout<<dp[a[i]]<<endl;
}

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

int a[393];//???????????????
int dp[394];//??????n??§???????????§?????????
int main(){
    int b;cin>>b;
    for(int c=0;c<b;c++){
	int d,e,f;
	cin>>d>>e>>f;
	for(d--;d<e;d++){
	    a[d]=max(a[d],f);
	    }
	}
   for(int i=0;i<393;i++){
       for(int j=i+1;j<=393;j++){
	   dp[j]=max(dp[j],dp[j-(i+1)]+a[i]);
	   }
       }	
    int n;cin>>n;
    vector<int>V;
    while(n--){
	int m;cin>>m;
	if(dp[m])V.push_back(dp[m]);
	else {puts("-1");return 0;}
	}
    for(int i:V)cout<<i<<endl;	
    }