#include using namespace std; #if __has_include() #include #endif using ll=long long; using ull=unsigned long long; using P=pair; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateistream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} templateistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define reps(i,a,n) for(int i=(a);i(0) ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } #ifdef LOCAL #include #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) templateostream &operator<<(ostream &os,const pair&p){os<>testcase; for(int i=0;i>n; ll ans=0; vector>left,right; rep(i,n){ int c; ll x,y; cin>>c>>x>>y; if(x==y){ ans+=x; continue; } if(c==0){ ans+=x; continue; } if(c==n){ ans+=y; continue; } if(xa(n,-1); sort(all(left)); priority_queueque; for(int i=n-1,j=(int)left.size();i>=0;i--){ while(j>0&&left[j-1].first>i){ que.push(left[--j].second); } if(que.empty())continue; ll x=que.top();que.pop(); a[i]=x; ans+=x; } while(!que.empty())que.pop(); for(int i=0,j=0;ib(n,-1); for(int i=0,j=0;i=0;i--)if(b[i]!=-1)b[j--]=b[i]; cout<