#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]; size_t s_min = 0, s_max = city_price.size(); while (s_min + 1 < s_max) { size_t mid = s_min + (s_max-s_min)/2; if (city_price[mid].first <= c) { s_min = mid; } else { s_max = mid; } } if (s_min + 1 == N)continue; s_min++; size_t next_city = city_price[s_min].first; size_t next_price = city_price[s_min].second; /*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[next_city], 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; }