import sys from collections import defaultdict def main(): W = int(sys.stdin.readline()) abc = [list(map(int, sys.stdin.readline().split())) for _ in range(W)] dp = defaultdict(list) dp[(1, 0)] = [(0, 0)] for i in range(1, W + 1): for s in [0, 1]: current_key = (i, s) if current_key not in dp: continue current_list = dp[current_key] for (good, money) in current_list: if s == 0: # Action 1: Work new_good = good new_money = money + abc[i-1][0] next_i = i + 1 next_s = 0 add_state(dp, next_i, next_s, new_good, new_money) # Action 2: School if i < W: next_i_school = i + 2 next_s_school = 0 b = abc[i][1] c = abc[i][2] new_good_school = good + b new_money_school = money - c add_state(dp, next_i_school, next_s_school, new_good_school, new_money_school) else: next_i_school = i + 1 next_s_school = 0 new_good_school = good new_money_school = money add_state(dp, next_i_school, next_s_school, new_good_school, new_money_school) # Action 3: Date (no effect) new_good_date = good new_money_date = money next_i_date = i + 1 next_s_date = 0 add_state(dp, next_i_date, next_s_date, new_good_date, new_money_date) else: # Forced to date b = abc[i-1][1] c = abc[i-1][2] new_good = good + b new_money = money - c next_i = i + 1 next_s = 0 add_state(dp, next_i, next_s, new_good, new_money) max_good = 0 for key in dp: i, s = key if i > W: for g, m in dp[key]: if m >= 0 and g > max_good: max_good = g print(max_good) def add_state(dp_dict, next_i, next_s, new_good, new_money): key = (next_i, next_s) new_list = [] added = False for g, m in dp_dict.get(key, []): if g >= new_good and m >= new_money: added = True break if not (new_good >= g and new_money >= m): new_list.append((g, m)) if not added: new_list.append((new_good, new_money)) new_list.sort(key=lambda x: (-x[0], -x[1])) filtered = [] max_m = -float('inf') for g, m in new_list: if m > max_m: filtered.append((g, m)) max_m = m dp_dict[key] = filtered if __name__ == "__main__": main()