//Zabutonみがある。 #include #include #include #include #define rep(i, n) for(i = 0; i < n; i++) using namespace std; typedef pair P; //(C, max(X, Y) - min(X, Y)) int n; vector

vec1; vector

vec2; signed main() { int i, ans = 0; cin >> n; rep(i, n) { int c, x, y; cin >> c >> x >> y; if (x > y) { //c枚以上で使う or x - yだけ罰金 vec2.push_back(P(c, x - y)); } else { //c枚未満で使う or y - xだけ罰金 vec1.push_back(P(c, y - x)); } ans += max(x, y); } sort(vec1.begin(), vec1.end()); sort(vec2.begin(), vec2.end(), greater

()); priority_queue, greater> que; rep(i, vec1.size()) { int c = vec1[i].first; int pena = vec1[i].second; //cout << "que.size(): " << que.size() << ", vec1[" << i << "]: c=" << c << ", pena=" << pena << endl; if (c == 0) { ans -= pena; } else { if (que.size() >= c) { int pena2 = que.top(); if (pena2 < pena) { ans -= pena2; que.pop(); que.push(pena); } else { ans -= pena; } } else { que.push(pena); } } } while (!que.empty()) que.pop(); rep(i, vec2.size()) { int c = n - vec2[i].first; int pena = vec2[i].second; //cout << "que.size(): " << que.size() << ", vec2[" << i << "]: c=" << c << ", pena=" << pena << endl; if (c == 0) { ans -= pena; } else { if (que.size() >= c) { int pena2 = que.top(); if (pena2 < pena) { ans -= pena2; que.pop(); que.push(pena); } else { ans -= pena; } } else { que.push(pena); } } } cout << ans << endl; return 0; }