#include using namespace std; #define all(x) begin(x), end(x) int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); // Id -> city + price map>> next; size_t N; cin >> N; vector>> cities; for (size_t c = 0; c < N; ++c) { size_t M; cin >> M; vector> id_prices; for (size_t w = 0; w < M; ++w) { size_t id, p; cin >> id >> p; id_prices.push_back({id, p}); next[id].push_back({c, p}); } cities.push_back(move(id_prices)); } for(auto& v: next) { std::sort(v.second.begin(), v.second.end()); } vector best_prices(N, 0); size_t best = 0; for (size_t c = 0; c < N; ++c) { auto& id_prices = cities[c]; for (size_t w = 0; w < id_prices.size(); ++w) { auto id = id_prices[w].first; auto price = id_prices[w].second; auto& city_price = next[id]; auto it = std::find(city_price.begin(), city_price.end(), make_pair(c, price)); assert (it != city_price.end()); it++; if (it == city_price.end()) { continue; } size_t next_city = it->first; size_t next_price = it->second; if (next_price > price) { size_t new_best = best_prices[c] + next_price - price; best_prices[next_city] = max(best_prices[new_best], new_best); best = max(best, new_best); } } if (c + 1 < N) { best_prices[c + 1] = max(best_prices[c+1], best_prices[c]); } } cout << best << endl; return 0; }