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: N = int(input())
s = []
l = []
p = []
for _ in range(N):
	temp_s,temp_l,temp_p = map(int,input().split())
	s.append(temp_s)
	l.append(temp_l)
	p.append(temp_p)

M = int(input())
w = [int(input()) for _ in range(M)]

max_M = max(w)

dp = [[-1 for _ in range(max_M + 1)] for _ in range(N+1)]

for i in range(N):
	for j in range(s[i],min(l[i]+1, max_M+1)):
		dp[i+1][j] = p[i]

for i in range(N):
	for j in range(max_M+1):
		if j < s[i]:
			dp[i+1][j] = max(dp[i+1][j], dp[i][j])
		elif j >= s[i]:
			if dp[i+1][j-s[i]] == -1:
				dp[i+1][j] = max(dp[i+1][j], dp[i][j])
			else:
				dp[i+1][j] = max(dp[i+1][j], dp[i][j], dp[i+1][j-s[i]] + p[i])
				

ans = []
for i in range(M):
	ans.append(dp[N][w[i]])

if ans.count(-1) >= 1:
	print(-1)
else:
	for a in ans:
		print(a)

Python: n=int(input())
phrase=[tuple(map(int,input().split())) for i in range(n)]
m=int(input())
inf=float('inf')
def main(phrase):
    point=[-1 for _ in range(394)]
    for x in phrase:
        s,l,p=x
        for k in range(s,l+1):
            point[k]=max(point[k],p)
    point[0]=0
    for i in range(1,394):
        for j in range(i):
            point[i]=max(point[i-j]+point[j],point[i])
    return point
ans=[]
dp=main(phrase)
for i in range(m):
    res=dp[int(input())]
    if res==-1:
        print(-1)
        break
    ans.append(res)
    if i==m-1:
        for i in range(m):
            print(ans[i])

Python: n=int(input())
s=[]
l=[]
p=[]
for i in range(n):
    ss,ll,pp=map(int,input().split())
    s.append(ss)
    l.append(ll)
    p.append(pp)
m=int(input())
w=[int(input()) for i in range(m)]
w_=max(w)
dp=[[-1]*(w_+1) for i in range(n+1)]
for i in range(n):
    for j in range(s[i],min(l[i]+1,w_+1)):
        dp[i+1][j]=p[i]
for i in range(n):
    for j in range(w_+1):
        if j<s[i]:
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        elif j>=s[i]:
            if dp[i+1][j-s[i]]==-1:
                dp[i+1][j]=max(dp[i][j],dp[i+1][j])
            else:
                dp[i+1][j]=max(dp[i][j],dp[i+1][j],dp[i+1][j-s[i]]+p[i])
ans=[]
for i in range(m):
    ans.append(dp[n][w[i]])
if ans.count(-1)>=1:
    print(-1)
else:
    for a in ans:
        print(a)

Python: n = int(input())
phrases = [tuple(map(int, input().split())) for _ in range(n)]
m = int(input())
melodies = [int(input()) for _ in range(m)]

max_length = max(melodies)
dp = [-1] * (max_length + 394)
dp[0] = 0

for i in range(max_length):
    if dp[i] == -1:
        continue
    for s, l, p in phrases:
        for j in range(s, l + 1):
            dp[i + j] = max(dp[i + j], dp[i] + p)

results = [None] * m
for i, melody in enumerate(melodies):
    result = dp[melody]
    if result == -1:
        print(-1)
        break
    results[i] = result
else:
    print('\n'.join(map(str, results)))

Python: n = int(input())
point = [-1] * 394
for _ in range(n):
  s, l, p = map(int, input().split())
  for i in range(s, l + 1):
    point[i] = max(point[i], p)

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

m = int(input())
ans = []
for _ in range(m):
  ans.append(point[int(input())])
if -1 in ans:print(-1)
else:print(*ans,sep="\n")

Python: n=int(input())
phrase=[tuple(map(int,input().split())) for i in range(n)]
m=int(input())
inf=float('inf')
def main(phrase):
    w=int(input())
    dp=[-1*inf for _ in range(w+1)]
    dp[0]=0
    for i in range(1,w+1):
        for x in phrase:
            s,l,p=x
            for k in range(s,l+1):
                if i-k<0:break
                dp[i]=max(dp[i-k]+p,dp[i])
    return dp[w] if dp[w]>=0 else -1
ans=[]
for i in range(m):
    res=main(phrase)
    if res==-1:
        print(-1)
        break
    ans.append(res)
    if i==m-1:
        for i in range(m):
            print(ans[i])

Python: 
import sys
sys.setrecursionlimit(100000)

n = int(input())
lyric = [tuple(map(int, input().split(" "))) for i in range(n)]
m = int(input())
melody = [int(input()) for i in range(m)]
max_melody = max(melody)
lis = [[0]+[None]*(max_melody) for j in range(n)]

def maxpoint(remin, j = n-1, _cache=lis):
    if remin < 0:
        return -1
    elif _cache[j][remin] is not None:
        return _cache[j][remin]
    else:
        if j >0:
            ans = maxpoint(remin, j-1)
        else:
            ans = -1
        for reduc in range(lyric[j][0], lyric[j][1] + 1):
            cand = maxpoint(remin - reduc, j)
            if cand != -1:
                ans = max(ans, cand + lyric[j][2])
        _cache[j][remin] = ans
        return ans

def points():
    l = []
    for i in range(m):
        l.append(maxpoint(melody[i]))
    return l

points = points()

if -1 in points:
    print(-1)
else:
    for i in range(m):
        print(points[i])

Python: from collections import defaultdict

max_phrases = defaultdict(int)
n = int(input())
for _ in range(n):
    s, l, p = map(int, input().split())
    for length in range(s, l + 1):
        max_phrases[length] = max(max_phrases[length], p)

m = int(input())
melodies = [int(input()) for _ in range(m)]

max_length = max(melodies)
dp = [-1] * (max_length + max(max_phrases))
dp[0] = 0

for i in range(max_length):
    c = dp[i]
    if c == -1:
        continue
    for length, p in max_phrases.items():
        dp[i + length] = max(dp[i + length], c + p)

results = [dp[melody] for melody in melodies]
print(-1 if -1 in results else '\n'.join(map(str, results)))

Python: n = int(input())
phrases = [tuple(map(int, input().split())) for _ in range(n)]
m = int(input())
melodies = [int(input()) for _ in range(m)]

max_length = max(melodies)
dp = [-1] * (max_length + 394)
dp[0] = 0

for i in range(max_length):
    c = dp[i]
    if c == -1:
        continue
    for s, l, p in phrases:
        for j in range(s, l + 1):
            dp[i + j] = max(dp[i + j], c + p)

results = [None] * m
for i, melody in enumerate(melodies):
    result = dp[melody]
    if result == -1:
        print(-1)
        break
    results[i] = result
else:
    print('\n'.join(map(str, results)))

Python: N = int(input())
P = [map(int, input().split()) for _ in range(N)]
M = int(input())
W = [int(input()) for _ in range(M)]
INF = 10 ** 9
maxW = 393
dp = [-INF] * (maxW + 1)
dp[0] = 0

for i in range(N):
    s, l, p = P[i]
    for j in range(s, maxW + 1):
        d = max(dp[max(0, j - l):max(1, j - s + 1)])
        dp[j] = max(dp[j], d + p)

ans = [dp[w] for w in W]
if min(ans) < 0:
    print(-1)
else:
    print(*ans, sep='\n')