DEBUG = False N = int(input().strip()) crane_prices = {} # (idx, [(city, price)] for n in range(N): list_len = int(input().strip()) for i in range(list_len): crane_id, price = [int(x) for x in input().strip().split(' ')] if crane_id not in crane_prices.keys(): crane_prices[crane_id] = [(n, price)] else: crane_prices[crane_id].append((n, price)) if DEBUG: print("crane_prices: ") print(crane_prices) best_prices = [0 for n in range(N)] # N-long array of best_prices graph = [[] for n in range(N)] for key in crane_prices.keys(): val = sorted(crane_prices[key]) for i, (city_id, buy_price) in enumerate(val): for to_idx in range(i+1, len(val)): to_city_id, sell_price = val[to_idx] profit = sell_price - buy_price if profit > 0: graph[city_id].append((to_city_id, profit)) if DEBUG: print(graph) for i in range(N-1): curr_price = best_prices[i] for city_id, price in graph[i]: # current city best_prices[city_id] = max(best_prices[city_id], curr_price + price) best_prices[i+1] = max(best_prices[i+1], best_prices[i]) if DEBUG: print("best_prices: ", best_prices) print(best_prices[-1])