import sys sys.setrecursionlimit(10 ** 6) int1 = lambda x: int(x) - 1 p2D = lambda x: print(*x, sep="\n") def II(): return int(sys.stdin.readline()) def MI(): return map(int, sys.stdin.readline().split()) def LI(): return list(map(int, sys.stdin.readline().split())) def LLI(rows_number): return [LI() for _ in range(rows_number)] def main(): def dfsl(i=0, like=0, money=0, last=False): if i >= n // 2: if last: money -= aa[n // 2] left.append((money, like, last)) return # バイトの場合 dfsl(i + 1, like, money + aa[i], last) # 学校の場合 dfsl(i + 2, like + bb[i + 1], money - cc[i + 1], i == n // 2 - 1) def dfsr(i=-1, like=0, money=0, first=False): if i == -1: i = n // 2 if i >= n: right.append((money, like, first)) return # バイトの場合 dfsr(i + 1, like, money + aa[i], first) # 学校の場合 if i == n // 2: first = True if i + 1 < n: dfsr(i + 2, like + bb[i + 1], money - cc[i + 1], first) n = II() aa = [] bb = [] cc = [] for _ in range(n): a, b, c = MI() aa += [a] bb += [b] cc += [c] # 学校に行く日を固定すると、次の日はデート、その他の日はバイトと一意に決まる # 期間を半分に分け、前後半ともに全列挙する left = [] dfsl() right = [] dfsr() # 他の結果と比べて、残金も少ないし好感度も低いものは不要なので削除する # 残金を降順にしたとき好感度は昇順になるはず # なっていない結果を削除 left.sort(key=lambda x: (x[2], -x[0], -x[1])) # print(left) plike = -1 plast = False nl = [] for i, (money, like, last) in enumerate(left): if plast != last: plike = -1 if like <= plike: continue nl.append((money, like, last)) plike, plast = like, last # print(nl) right.sort(key=lambda x: (x[2], -x[0], -x[1])) # print(right) plike = -1 pfirst = False nr = [] for i, (money, like, first) in enumerate(right): if pfirst != first: plike = -1 if like <= plike: continue nr.append((money, like, first)) plike, pfirst = like, first # print(nr) # left,rightともに残金でソートし直してしゃくとり法 # leftは左から、rightは右から、残金の合計が負にならないように動かす # ただし、last,firstがともにTrueのときは選べない nl.sort() nr.sort() #print(nl) #print(nr) j = len(nr) - 1 ans = 0 for i in range(len(nl)): lm, ll, last = nl[i] while 1: rm, rl, first = nr[j] if (not (last and first)) and lm + rm >= 0 and ll + rl > ans: ans = ll + rl #print(ans, ll, rl, lm, rm) if j == 0 or lm + nr[j - 1][0] < 0: break j -= 1 print(ans) main()