CodeEff/ECCO huggingface dataset:
# Original solution
# coding: utf-8
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Nから0にする
T = ir()

@lru_cache(None)
def F(x, A, B, C, D):
    if x == 1:
        return D
    elif x <= 0:
        return INF
    if x&1:
        a = min(F(x//2, A, B, C, D) + D + A, F((x+1)//2, A, B, C, D) + D + A)
    else:
        a = F(x//2, A, B, C, D) + A
    cnt2 = 0
    y = x
    while y%3 != 0:
        y -= 1
        cnt2 += 1
    b = F(y//3, A, B, C, D) + B + cnt2 * D
    if (x+1)%3 == 0:
        t = F((x+1)//3, A, B, C, D) + B + D
        b = min(b, t)
    cnt3 = 0
    y = x
    while y%5 != 0:
        y -= 1
        cnt3 += 1
    c = min(F(y//5, A, B, C, D) + C + cnt3 * D, F((y+5)//5, A, B, C, D) + C + (5-cnt3) * D)
    ret = min(a, b, c)
    if x < 10 ** 12 or D < 10 ** 9:
        d = x * D
        ret = min(ret, d)
    return ret

INF = float('inf')
for _ in range(T):
    N, A, B, C, D = lr()
    answer = F(N, A, B, C, D)
    print(answer)


# Optimized solution
# coding: utf-8
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Nから0にする
T = ir()

@lru_cache(None)
def F(x, A, B, C, D):
    if x == 1:
        return D
    elif x <= 0:
        return INF
    if x&1:
        a = min(F(x//2, A, B, C, D) + D + A, F((x+1)//2, A, B, C, D) + D + A)
    else:
        a = F(x//2, A, B, C, D) + A
    cnt2 = 0
    y = x
    while y%3 != 0:
        y -= 1
        cnt2 += 1
    b = F(y//3, A, B, C, D) + B + cnt2 * D
    if (x+1)%3 == 0:
        t = F((x+1)//3, A, B, C, D) + B + D
        b = min(b, t)
    cnt3 = 0
    y = x
    while y%5 != 0:
        y -= 1
        cnt3 += 1
    c = min(F(y//5, A, B, C, D) + C + cnt3 * D, F((y+5)//5, A, B, C, D) + C + (5-cnt3) * D)
    d = x * D
    ret = min(a, b, c, d)
    return ret

INF = float('inf')
for _ in range(T):
    N, A, B, C, D = lr()
    answer = F(N, A, B, C, D)
    print(answer)
# Original solution
import math
from functools import lru_cache

T = int(eval(input()))


class Resolver:
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    @lru_cache(maxsize=None)
    def resolve(self, n):
        if n == 0:
            return 0
        elif n == 1:
            return self.d
        else:
            div5f = n // 5
            div5c = (n + 4) // 5
            div3f = n // 3
            div3c = (n + 2) // 3
            div2f = n // 2
            div2c = (n + 1) // 2
            return min(
                self.d * n,
                self.d * abs(n - div5f * 5) + self.c + self.resolve(div5f),
                self.d * abs(n - div5c * 5) + self.c + self.resolve(div5c),
                self.d * abs(n - div3f * 3) + self.b + self.resolve(div3f),
                self.d * abs(n - div3c * 3) + self.b + self.resolve(div3c),
                self.d * abs(n - div2f * 2) + self.a + self.resolve(div2f),
                self.d * abs(n - div2c * 2) + self.a + self.resolve(div2c),
            )


for _ in range(T):
    N, A, B, C, D = list(map(int, input().split(' ')))
    resolver = Resolver(A, B, C, D)
    print((resolver.resolve(N)))


# Optimized solution
from functools import lru_cache

T = int(eval(input()))


def resolver(a, b, c, d):
    @lru_cache(maxsize=None)
    def _resolver(n):
        if n == 0:
            return 0
        elif n == 1:
            return d
        else:
            div5f = n // 5
            div5c = (n + 4) // 5
            div3f = n // 3
            div3c = (n + 2) // 3
            div2f = n // 2
            div2c = (n + 1) // 2
            return min(
                d * n,
                d * abs(n - div5f * 5) + c + _resolver(div5f),
                d * abs(n - div5c * 5) + c + _resolver(div5c),
                d * abs(n - div3f * 3) + b + _resolver(div3f),
                d * abs(n - div3c * 3) + b + _resolver(div3c),
                d * abs(n - div2f * 2) + a + _resolver(div2f),
                d * abs(n - div2c * 2) + a + _resolver(div2c),
            )

    return _resolver


for _ in range(T):
    N, A, B, C, D = list(map(int, input().split(' ')))
    print((resolver(A, B, C, D)(N)))
# Original solution
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(10**7)

t = int(eval(input()))
for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    memo = {0: 0, 1: d}
    def cost(N):
        if N in memo:
            return memo[N]
        ans = N * d
        ks = [2, 3, 5]
        abc = [a, b, c]
        for i in range(3):
            k = ks[i]
            coin = abc[i]
            div, mod = divmod(N, k)
            pay = mod * d + coin

            # D枚コインを払って1だけ増減させる。
            # その際に行き着く先として、div(減らす場合) or div+1(増やす場合)
            # 増やす場合は、現在の状態から、最寄りの倍数まで足す必要があり、これはmodからkまでの距離と等しい。
            ans = min(ans, pay + cost(div))
            if mod == 0:
                continue
            pay = (k - mod) * d + coin
            ans = min(ans, pay + cost(div + 1))
        memo[N] = ans
        return ans
    print((cost(n)))

# Optimized solution
#!/usr/bin/env python3

N = 0
A = 0
B = 0
C = 0
D = 0
cost_result = {} # ある数に達するために必要なコインの枚数
each_cost = {} # 与えられたコスト

def cost(target):
    """
    Args:
        target: 目標とする数字

    Returns:
        result: その数字に達するまでに必要なコスト
    """
    if target in cost_result:
        return cost_result[target]

    else:
        result_dict = {}
        for i in [2, 3, 5]:
            if target % i == 0:
                result_dict[i] = cost(target//i) + each_cost[i]
            else:
                result_dict[i] = min(
                    cost(target//i) + each_cost[i] + D * (target % i),
                    cost((target//i)+1) + each_cost[i] + D * (i - target % i)
                )
        simplest = target * D
        result = min(min(result_dict.values()), simplest)
        cost_result[target] = result
        return result



if __name__ == "__main__":
    T = int(eval(input()))
    for _ in range(T):
        N, A, B, C, D = list(map(int, input().split()))

        each_cost[2] = A
        each_cost[3] = B
        each_cost[5] = C
        cost_result[1] = D
        cost_result = {0:0, 1:D}

        print((cost(N)))
# Original solution
import sys
input = sys.stdin.readline
from functools import lru_cache

T=int(eval(input()))
for tests in range(T):
    N,A,B,C,D=list(map(int,input().split()))

    DP=[N*D]*(10**5)
    DP[0]=0

    for i in range(10**5):
        for k in range(i-10,i+10):
            if 0<=k<10**5 and DP[k]>DP[i]+abs(i-k)*D:
                DP[k]=DP[i]+abs(i-k)*D
        #if 0<=i+1<10**5 and DP[i+1]>DP[i]+D:
        #    DP[i+1]=DP[i]+D
            
        #if 0<=i-1<10**5 and DP[i-1]>DP[i]+D:
        #    DP[i-1]=DP[i]+D

        if 0<=2*i<10**5 and DP[2*i]>DP[i]+A:
            DP[2*i]=DP[i]+A

        if 0<=3*i<10**5 and DP[3*i]>DP[i]+B:
            DP[3*i]=DP[i]+B

        if 0<=5*i<10**5 and DP[5*i]>DP[i]+C:
            DP[5*i]=DP[i]+C

    @lru_cache(maxsize=None)
    def calc(x):
        if x<=10:
            return DP[x]

        ANS=x*D

        two=x//2*2

        ANS=min(ANS,abs(two-x)*D+A+calc(two//2))
        ANS=min(ANS,abs(two+2-x)*D+A+calc(two//2+1))

        three=x//3*3
        ANS=min(ANS,abs(three-x)*D+B+calc(three//3))
        ANS=min(ANS,abs(three+3-x)*D+B+calc(three//3+1))

        five=x//5*5
        ANS=min(ANS,abs(five-x)*D+C+calc(five//5))
        ANS=min(ANS,abs(five+5-x)*D+C+calc(five//5+1))

        return ANS

    print((calc(N)))

    
        


# Optimized solution
import sys
input = sys.stdin.readline
from functools import lru_cache

T=int(eval(input()))
for tests in range(T):
    N,A,B,C,D=list(map(int,input().split()))

    @lru_cache(maxsize=None)
    def calc(x):
        if x==1:
            return D

        ANS=x*D

        two=x//2*2
        if two//2<x:
            ANS=min(ANS,abs(two-x)*D+A+calc(two//2))
        if two//2+1<x:
            ANS=min(ANS,abs(two+2-x)*D+A+calc(two//2+1))

        three=x//3*3
        if three//3<x:
            ANS=min(ANS,abs(three-x)*D+B+calc(three//3))
        if three//3+1<x:
            ANS=min(ANS,abs(three+3-x)*D+B+calc(three//3+1))

        five=x//5*5
        if five//5<x:
            ANS=min(ANS,abs(five-x)*D+C+calc(five//5))
        if five//5+1<x:
            ANS=min(ANS,abs(five+5-x)*D+C+calc(five//5+1))

        return ANS

    print((calc(N)))
# Original solution
import sys
from functools import lru_cache
sys.setrecursionlimit(10**9)

@lru_cache(None)
def f(n,a,b,c,d):
  if n==0:return 0
  if n==1:return d
  if n==2:return min(d*2,a+d)
  if n==3:return min(d*3,d+a+d,b+d)
  if n==4:return min(d*4,a+a+d,d+b+d,d+c+d)
  if n==5:return min(d*5,d+a+a+d,d+d+b+d,d+a+b+d,c+d)
  if n==6:return min(d*6,a+b+d,a+d+a+d,b+d+b+d,d+c+d)
  # print(n,a,b,c,d)
  p=n*d
  for i in range(-10, 11):
    nn=n+i
    if nn<0:continue
    if nn%2==0and nn//2<n:p=min(p,f(nn//2,a,b,c,d)+abs(i)*d+a)
    if nn%3==0and nn//3<n:p=min(p,f(nn//3,a,b,c,d)+abs(i)*d+b)
    if nn%5==0and nn//5<n:p=min(p,f(nn//5,a,b,c,d)+abs(i)*d+c)
  return p

for _ in range(int(eval(input()))):
  n,a,b,c,d = list(map(int,input().split()))
  print((f(n,a,b,c,d)))

# Optimized solution
from functools import lru_cache

def solve(n,a,b,c,d):
    @lru_cache(None)
    def rec(cur):
        if cur == 0:    return 0
        if cur == 1:    return d
        ret = cur * d
        p,q = divmod(cur, 2)
        if q == 0:  ret = min(ret, rec(p) + a)
        if q == 1:  ret = min(ret, rec(p) + a + d, rec(p + 1) + a + d)
        p,q = divmod(cur, 3)
        if q == 0:  ret = min(ret, rec(p) + b)
        if q == 1:  ret = min(ret, rec(p) + b + d)
        if q == 2:  ret = min(ret, rec(p) + b + d * 2, rec(p + 1) + b + d)
        p,q = divmod(cur, 5)
        if q == 0:  ret = min(ret, rec(p) + c)
        if q == 1:  ret = min(ret, rec(p) + c + d)
        if q == 2:  ret = min(ret, rec(p) + c + d * 2)
        if q == 3:  ret = min(ret, rec(p) + c + d * 3, rec(p + 1) + c + d * 2)
        if q == 4:  ret = min(ret, rec(p) + c + d * 4, rec(p + 1) + c + d)
        return ret

    return rec(n)

for _ in range(int(eval(input()))):
    n,a,b,c,d = list(map(int,input().split()))
    print((solve(n,a,b,c,d)))
# Original solution
from heapq import heappop, heappush

T = int(input())
ans = []
for _ in range(T):
    N, A, B, C, D = map(int, input().split())

    Q = [(0, N)]
    # already processed
    S = set()
    an = D * N
    while Q:
        cost, num = heappop(Q)
        if num in S:
            continue
        an = min(an, cost + num * D)
        if num == 1:
            break
        S.add(num)

        q, r = divmod(num, 2)
        if r < 2:
            heappush(Q, (cost + A + r * D, q))
        if r > 0:
            heappush(Q, (cost + A + (2 - r) * D, q + 1))

        q, r = divmod(num, 3)
        if r < 2:
            heappush(Q, (cost + B + r * D, q))
        if r > 0:
            heappush(Q, (cost + B + (3 - r) * D, q + 1))

        q, r = divmod(num, 5)
        if r < 3:
            heappush(Q, (cost + C + r * D, q))
        if r > 0:
            heappush(Q, (cost + C + (5 - r) * D, q + 1))
    ans.append(an)

print(*ans, sep="\n")


# Optimized solution
from heapq import heappop, heappush

T = int(input())
ans = []
for _ in range(T):
    N, A, B, C, D = map(int, input().split())

    Q = [(0, N)]
    # already processed
    S = set()
    an = D * N
    while Q:
        cost, num = heappop(Q)
        if num in S:
            continue
        an = min(an, cost + num * D)
        if num == 1:
            break
        S.add(num)

        q, r = divmod(num, 2)
        if r < 2:
            heappush(Q, (cost + A + r * D, q))
        if r > 0:
            heappush(Q, (cost + A + (2 - r) * D, q + 1))

        q, r = divmod(num, 3)
        if r < 2:
            heappush(Q, (cost + B + r * D, q))
        if r > 1:
            heappush(Q, (cost + B + (3 - r) * D, q + 1))

        q, r = divmod(num, 5)
        if r < 3:
            heappush(Q, (cost + C + r * D, q))
        if r > 2:
            heappush(Q, (cost + C + (5 - r) * D, q + 1))
    ans.append(an)

print(*ans, sep="\n")
# Original solution
T = int(eval(input()))

while(T > 0):
    N, A, B, C, D = list(map(int, input().split()))
    dp = {}

    def d(n):
        if n == 0:
            return 0
        if n == 1:
            return D

        if n in dp:
            return dp[n]

        ret = min(
            D * n,
            D * abs(n - (n // 2) * 2) + A + d(n // 2),
            D * abs(n - ((n+1) // 2) * 2) + A + d((n+1) // 2),
            D * abs(n - (n // 3) * 3) + B + d(n // 3),
            D * abs(n - ((n + 2) // 3) * 3) + B + d((n + 2) // 3),
            D * abs(n - (n // 5) * 5) + C + d(n // 5),
            D * abs(n - ((n + 4) // 5) * 5) + C + d((n + 4) // 5),
        )

        dp[n] = ret
        return ret

    print((d(N)))
    T -= 1

# Optimized solution
T = int(eval(input()))

while(T > 0):
    N, A, B, C, D = list(map(int, input().split()))
    memo = {}
    def d(n):
        if n == 0:
            return 0

        if n == 1:
            return D

        if n in memo:
            return memo[n]

        ret = n * D

        if (n % 2 == 0):
            ret = min(ret, A + d(n // 2))
        else:
            ret = min(ret, (n%2)*D + A + d(n // 2), (2-n%2)*D + A + d((n+(2-n%2))//2))

        if (n % 3 == 0):
            ret = min(ret, B + d(n // 3))
        else:
            ret = min(ret, (n%3)*D + B + d(n // 3), (3-n%3)*D + B + d((n+(3-n%3))//3))

        if (n % 5 == 0):
            ret = min(ret, C + d(n // 5))
        else:
            ret = min(ret, (n%5)*D + C + d(n // 5), (5-n%5)*D + C + d((n+(5-n%5))//5))

        memo[n] = ret
        return ret

    print((d(N)))
    T -= 1
# Original solution
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc

def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check[0]) if 0 in check else check[n]+n*d
    if n//ttf==0:
        check[n//ttf]=min(check[n]+(n%ttf)*d,check[n//ttf]) if n//ttf in check else check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(eval(input()))
for i in range(t):
    N,*b,d=list(map(int,input().split()))
    check={N:0}
    dfs(N)
    print((check[0]))


# Optimized solution
def f(n):
 if (m:=s.get(n,-1))<0:s[n]=m=min([d*n]+[abs(p*k-n)*d+c+f(k)for p,c in zip(a,b)for k in(n//p,0--n//p)])
 return m
exec("n,*b,d=map(int,input().split());a=2,3,5;s={0:0,1:d};print(f(n));"*int(eval(input())))
# Original solution
check=dict()
#ttfは235、chaはabc

def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    if x1 in check:
        if check[x1]>check[n]+x2*d+cha:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)
    else:
        check[x1]=check[n]+x2*d+cha
        dfs(x1)

    #最寄りまで+1してく場合
    x1,x2=n//ttf+1,ttf-n%ttf
    if x1 in check:
        if check[x1]>check[n]+x2*d+cha:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)
    else:
        check[x1]=check[n]+x2*d+cha
        dfs(x1)


def dfs(n):
    global b
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(eval(input()))
for i in range(t):
    N,*b,d=list(map(int,input().split()))
    check={N:0,0:N*d}
    dfs(N)
    print((check[0]))


# Optimized solution
def dfs(n):
    global b,check,d
    #ttfは235、chaはabc
    for ttf,cha in zip([2,3,5],b):
        #-1ずつしていく場合
        check[0]=min(check[n]+n*d,check[0])

        #最寄りまで-してく場合
        x1,x2=n//ttf,n%ttf
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

        #最寄りまで+1してく場合
        x1,x2=n//ttf+1,ttf-n%ttf
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

t=int(eval(input()))
for i in range(t):
    N,*b,d=list(map(int,input().split()))
    check={N:0,0:N*d}
    dfs(N)
    print((check[0]))
# Original solution
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

setrecursionlimit(10**6)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: list(map(int, stdin.readline().split()))
rlf = lambda: list(map(float, stdin.readline().split()))

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def main():
	n = int(rl())
	A = []
	for _ in range(n):
		w, s, v = rli()
		A.append((w, s, v))
	ans = 0
	A.sort(key = lambda I: (I[0] + I[1]))
	maxs = 2*10**4 + 100
	dp = [0 for _ in range(maxs+1)]
	for w, s, v in A:
		for i in range(maxs, -1, -1):
			if i - w < 0: continue
			if i - w > s: continue
			dp[i] = max(dp[i], dp[i-w] + v)
			ans = max(ans, dp[i])	
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

# Optimized solution
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

setrecursionlimit(10**6)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: list(map(int, stdin.readline().split()))
rlf = lambda: list(map(float, stdin.readline().split()))

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def main():
	n = int(rl())
	A = []
	mw, ms = 0, 0
	for _ in range(n):
		w, s, v = rli()
		mw, ms = max(mw, w), max(ms, s)
		A.append((w, s, v))
	ans = 0
	A.sort(key = lambda I: (I[0] + I[1]))
	maxs = mw + ms + 100
	dp = [0 for _ in range(maxs+1)]
	for w, s, v in A:
		for i in range(maxs, -1, -1):
			if i - w < 0: break
			if i - w > s: continue
			dp[i] = max(dp[i], dp[i-w] + v)
			ans = max(ans, dp[i])	
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()
# Original solution
import sys

n = int(eval(input()))
blocks = []
for line in sys.stdin.readlines():
    w, s, v = list(map(int, line.split()))
    blocks.append((w + s, w, s, v))
blocks.sort()

dp = [-1] * 20001
dp[0] = 0
for _, w, s, v in blocks:
    for i in range(min(s, 20000 - w), -1, -1):
        dp[i + w] = max(dp[i + w], dp[i] + v)
print((max(dp)))


# Optimized solution
import sys

n = int(eval(input()))
blocks = []
for line in sys.stdin.readlines():
    w, s, v = list(map(int, line.split()))
    blocks.append((w + s, w, s, v))
blocks.sort()

dp = [-1] * 20001
dp[0] = 0
for _, w, s, v in blocks:
    for i in range(s, -1, -1):
        if dp[i] == -1:
            continue
        dp[i + w] = max(dp[i + w], dp[i] + v)
print((max(dp)))
# Original solution
n = int(eval(input()))
dp = [0] * (n * 10 ** 4 + 1)
bs = [list(map(int, input().split())) for _ in range(n)]
bs.sort(key=lambda x: x[0] + x[1])
for w, s, v in bs:
    for i in range(w + s, w - 1, -1):
        dpw = dp[i - w] + v
        if dpw > dp[i]:
            dp[i] = dpw
print((max(dp)))


# Optimized solution
def f(n):
    dp = [0] * (n * 10 ** 4 + 1)
    bs = [list(map(int, input().split())) for _ in range(n)]
    bs.sort(key=lambda x: x[0] + x[1])
    for w, s, v in bs:
        for i in range(w + s, w - 1, -1):
            dpw = dp[i - w] + v
            if dpw > dp[i]:
                dp[i] = dpw
    print((max(dp)))


n = int(eval(input()))
f(n)
# Original solution
def f(n):
    dp = [0] * (n * 10 ** 4 + 1)
    bs = [list(map(int, input().split())) for _ in range(n)]
    bs.sort(key=lambda x: x[0] + x[1])
    for w, s, v in bs:
        for i in range(w + s, w - 1, -1):
            dpw = dp[i - w] + v
            if dpw > dp[i]:
                dp[i] = dpw
    print((max(dp)))


n = int(eval(input()))
f(n)


# Optimized solution
def f(n):
    mx = 0
    dp = [0] * (n * 10 ** 4 + 1)
    bs = [list(map(int, input().split())) for _ in range(n)]
    bs.sort(key=lambda x: x[0] + x[1])
    for w, s, v in bs:
        for i in range(w + s, w - 1, -1):
            dpw = dp[i - w] + v
            if dpw > dp[i]:
                dp[i] = dpw
                if dpw > mx:
                    mx = dpw
    print(mx)


n = int(eval(input()))
f(n)
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from functools import cmp_to_key
    n=int(eval(input()))
    B=[list(map(int,input().split())) for _ in range(n)]
    def cmp(a,b):
        va=min(a[1],b[1]-a[0])
        vb=min(b[1],a[1]-b[0])
        if(va==vb): return 0
        return -1 if(va>vb) else 1
    B.sort(key=cmp_to_key(cmp))
    dp=[-INF]*(30101)
    dp[0]=0
    for i in range(n):
        w,s,v=B[i]
        ndp=dp[:]
        for total in range(20101):
            if(total<=s):
                ndp[total+w]=max(ndp[total+w],dp[total]+v)
        dp=ndp[:]
    print((max(dp[:20101])))
resolve()

# Optimized solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from functools import cmp_to_key
    n=int(eval(input()))
    B=[list(map(int,input().split())) for _ in range(n)]
    def cmp(a,b):
        va=min(a[1],b[1]-a[0])
        vb=min(b[1],a[1]-b[0])
        if(va==vb): return 0
        return -1 if(va>vb) else 1
    B.sort(key=cmp_to_key(cmp))
    maxS=20000
    dp=[-INF]*(maxS+1)
    dp[0]=0
    for i in range(n):
        w,s,v=B[i]
        ndp=dp[:]
        for total in range(maxS+1):
            if(total<=s and total+s<=maxS):
                ndp[total+w]=max(ndp[total+w],dp[total]+v)
        dp=ndp[:]
    print((max(dp)))
resolve()
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from functools import cmp_to_key
    n=int(eval(input()))
    B=[list(map(int,input().split())) for _ in range(n)]
    def cmp(a,b):
        va=min(a[1],b[1]-a[0])
        vb=min(b[1],a[1]-b[0])
        if(va==vb): return 0
        return -1 if(va>vb) else 1
    B.sort(key=cmp_to_key(cmp))
    maxS=20000
    dp=[-INF]*(maxS+1)
    dp[0]=0
    for i in range(n):
        w,s,v=B[i]
        ndp=dp[:]
        for total in range(maxS+1):
            if(total<=s and total+s<=maxS):
                ndp[total+w]=max(ndp[total+w],dp[total]+v)
        dp=ndp[:]
    print((max(dp)))
resolve()

# Optimized solution
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()

def resolve():
    n = int(eval(input()))
    WSV = [tuple(map(int, input().split())) for _ in range(n)]
    WSV.sort(key = lambda tup:tup[0] + tup[1])

    # dp[i][w] : i 番目まで見て、total weight が w のときの max value
    # solid_max <= 10^4 なので、total weight > 10^4 は考えなくて良い
    res = 0
    solid_max = 10 ** 4
    dp = [-1] * (solid_max + 1)
    dp[0] = 0

    for w0, s0, v in WSV:
        for w in range(solid_max, -1, -1):
            if dp[w] == -1:
                continue
            if w > s0: # w <= s0
                continue
            if w + w0 > solid_max:
                res = max(res, dp[w] + v)
            else:
                dp[w + w0] = max(dp[w + w0], dp[w] + v)

    res = max(res, max(dp))
    print(res)
resolve()
# Original solution
n=int(eval(input()));
ans=0;
p=[0]*22222;
for w,s,v in sorted([list(map(int,input().split()))for _ in[0]*n],key=lambda a:a[0]+a[1]):
 for j in range(s,-1,-1):
  p[j+w]=max(p[j+w],p[j]+v);
  ans=max(ans,p[j+w]);
print(ans)


# Optimized solution
p=[0]*6**6
for w,s,v in sorted([list(map(int,input().split()))for _ in[0]*int(eval(input()))],key=lambda a:a[0]+a[1]):
 for j in range(s,-1,-1):p[j+w]=max(p[j+w],p[j]+v)
print((max(p)))