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 copy
n_phrase = int(input())
phrases = []
for _ in range(n_phrase):
    l, h, s = map(int, input().split(" "))
    phrases.append([l, h, s])
n_melodies = int(input())
answer = []

for _ in range(n_melodies):
    length = int(input())
    target = [0 for n in range(length + 1)]
    for phrase in phrases:
        l, h, sc = phrase
        # print(l, h, sc)
        temp_t = copy.copy(target)
        for i, t in enumerate(temp_t):
            if t:
                for jj in range(i + l, min(h + i + 1, length + 1)):
                    temp_t[jj] = max(temp_t[jj], t + sc)
        for i in range(l, h + 1):
            # print(i, l, h, sc)
            if i > length:
                break
            temp_t[i] = max(temp_t[i], sc)
        # print(temp_t)
        target = temp_t
    # print(target)
    if target[length]:
        answer.append(target[length])
    else:
        print(-1)
        break
else:
    for a in answer:
        print(a)

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 _cache[j][remin] is not None:
        return _cache[j][remin]
    else:
        if j > 0:
            ans = maxpoint(remin, j-1)
        else:
            ans = -1
        if lyric[j][0] <= remin:
            for reduc in range(lyric[j][0], min(lyric[j][1], remin) + 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: # -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class SegTree:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """
 
    def __init__(self, n, func, init):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param init: 要素の初期値(単位元)
        """
        self.n = n
        self.func = func
        self.init = init
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.init] * (n2 << 1)
 
    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = self.func(x, self.tree[i ^ 1])
            i >>= 1
 
    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.init
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

N = INT()
phrases = []
for i in range(N):
    l, r, p = MAP()
    phrases.append((l, r, p))
M = INT()
melody = [0] * M
for i in range(M):
    melody[i] = INT()

mxm = max(melody)
dp = [SegTree(mxm+1, max, 0) for i in range(N+1)]
for i in range(1, N+1):
    l, r, p = phrases[i-1]
    for j in range(mxm+1):
        # 上からの遷移
        mx = dp[i-1].query(j, j+1)
        l2, r2 = max(0, j-r), max(0, j-l+1)
        # 取ってこれる範囲があれば、左上と左からの遷移をする
        if not (l2 == r2 == 0):
            mx = max(
                mx,
                dp[i-1].query(l2, r2) + p,
                dp[i].query(l2, r2) + p,
            )
        dp[i].update(j, mx)

ans = [0] * M
for i, mel in enumerate(melody):
    ans[i] = dp[N].query(mel, mel+1)
if min(ans) == 0:
    print(-1)
else:
    [print(a) for a in ans]

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 s, l, p in phrases:
    for i in range(max_length):
        if dp[i] > -1:
            for j in range(s, l + 1):
                dp[i + j] = max(dp[i + j], dp[i] + p)

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

Python: def main():
    n=int(input())
    slp=[list(map(int,input().split())) for _ in [0]*n]
    m=int(input())
    W=[int(input()) for _ in [0]*m]
    ans=[]
    
    point=[0]*393
    for s,l,p in slp:
        for i in range(s,l+1):
            point[i-1]=max(point[i-1],p)
    
    memo=[0]*(394)
    for i in range(393):
        for l,p in enumerate(point[:393-i]):
            memo[i+l+1]=max(memo[i+l+1],memo[i]+p)
    
    for w in W:
        ans.append(memo[w])
    if 0 in ans:
        print(-1)
    else:
        for i in ans:
            print(i)
if __name__ == '__main__':
    main()