#include using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; template using max_heap = priority_queue; template using min_heap = priority_queue, greater>; #define rep(i, l, r) for (ll i = (l); i < (r); i++) #define rrep(i, r, l) for (ll i = (r); i-- > (l);) #define all(x) begin(x), end(x) template bool chmin(T& lhs, T rhs) { return lhs > rhs ? (lhs = rhs, true) : false; } template bool chmax(T& lhs, T rhs) { return lhs < rhs ? (lhs = rhs, true) : false; } struct IOIO { IOIO() { cin.tie(0)->sync_with_stdio(0); } } ioio; template ostream& operator<<(ostream& os, const pair& p) { os << '(' << p.first << ", " << p.second << ')'; return os; } template ostream& operator<<(ostream& os, const vector& vs) { os << '{'; rep(i, 0, (int)vs.size()) os << vs[i] << (i + 1 == (int)vs.size() ? "" : ", "); os << '}'; return os; } template ostream& operator<<(ostream& os, const set& vs) { os << '{'; for (auto it = vs.begin(); it != vs.end(); it++) { if (it != vs.begin()) { os << ", "; } os << *it; } os << '}'; return os; } template ostream& operator<<(ostream& os, const map& vs) { os << '{'; for (auto it = vs.begin(); it != vs.end(); it++) { if (it != vs.begin()) { os << ", "; } os << *it; } os << '}'; return os; } #ifdef DEBUG void dump_func() { cerr << endl; } template void dump_func(Head&& head, Tail&&... tail) { cerr << head; if (sizeof...(Tail) > 0) { cerr << ", "; } dump_func(std::move(tail)...); } #define dump(...) cerr << "[" + string(#__VA_ARGS__) + "] ", dump_func(__VA_ARGS__) #else #define dump(...) static_cast(0) #endif void solve() { int n; cin >> n; struct Card { int i; int c; ll x, y; }; vector cards(n); rep(i, 0, n) cin >> cards[i].c >> cards[i].x >> cards[i].y, cards[i].i = i; ll ans = 0; for (auto& card: cards) { ll mn = min(card.x, card.y); ans += mn; card.x -= mn; card.y -= mn; } vector used(n); const char X = 'X'; const char Y = 'Y'; dump(used); { min_heap> que; vector a; for (auto card: cards) if (card.x < card.y) a.push_back(card); sort(all(a), [](auto lhs, auto rhs) { return lhs.c < rhs.c; }); rep(i, 0, ssize(a)) { que.emplace(a[i].y, a[i].i); if (que.size() > a[i].c) { que.pop(); } } while (!que.empty()) { auto [y, i] = que.top(); que.pop(); ans += y; used[i] = Y; } rep(i, 0, ssize(a)) { if (used[a[i].i] == 0) { used[a[i].i] = X; ans += a[i].x; } } } dump(used); { min_heap> que; vector a; for (auto card: cards) { if (card.x == card.y) { ans += card.x; used[card.i] = Y; } else if (card.x > card.y) { que.emplace(card.c, card.i); } } int used_num = n - count(all(used), 0); while (!que.empty()) { auto [c, i] = que.top(); if (c >= used_num) { que.pop(); ans += cards[i].x; used[i] = X; used_num++; } else { break; } } } dump(used); { min_heap> que; vector a; rep(i, 0, n) if (used[i] == 0) { auto card = cards[i]; card.c = n - card.c; a.push_back(card); } sort(all(a), [](auto lhs, auto rhs) { return lhs.c < rhs.c; }); rep(i, 0, ssize(a)) { que.emplace(a[i].x, a[i].i); if (que.size() > a[i].c) { que.pop(); } } while (!que.empty()) { auto [x, i] = que.top(); que.pop(); ans += x; used[i] = X; } rep(i, 0, ssize(a)) { if (used[a[i].i] == 0) { used[a[i].i] = Y; ans += a[i].y; } } } assert((int)count(all(used), 0) == 0); dump(used); cout << ans << '\n'; } int main() { int t = 1; while (t--) solve(); }