#ifdef LOCAL //#define _GLIBCXX_DEBUG #endif //#pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include using namespace std; typedef long long ll; typedef long double ld; typedef pair P; typedef pair Pi; typedef vector Vec; typedef vector Vi; typedef vector Vs; typedef vector Vc; typedef vector

VP; typedef vector> VV; typedef vector> VVi; typedef vector> VVc; typedef vector>> VVV; typedef vector>>> VVVV; #define endl '\n' #define REP(i, a, b) for(ll i=(a); i<(b); i++) #define PER(i, a, b) for(ll i=(a); i>=(b); i--) #define rep(i, n) REP(i, 0, n) #define per(i, n) PER(i, n, 0) const ll INF = 1e18+18; const ll MOD = 1000000007; #define Yes(n) cout << ((n) ? "Yes" : "No") << endl; #define YES(n) cout << ((n) ? "YES" : "NO") << endl; #define ALL(v) v.begin(), v.end() #define rALL(v) v.rbegin(), v.rend() #define pb(x) push_back(x) #define mp(a, b) make_pair(a,b) #define Each(a, b) for(auto &a :b) #define rEach(i, mp) for (auto i = mp.rbegin(); i != mp.rend(); ++i) #ifdef LOCAL #define dbg(x_) cerr << #x_ << ":" << x_ << endl; #define dbgmap(mp) cerr << #mp << ":"<first <<":"<second << endl;} #define dbgset(st) cerr << #st << ":"< bool chmax(T &a, const T &b) { if(a < b) { a = b; return true; } return false; } template bool chmin(T &a, const T &b) { if(b < a) { a = b; return true; } return false; } template ostream &operator<<(ostream &s, const pair &p) { return s<<"("< istream &operator>>(istream &i, vector &v) { rep(j, v.size())i>>v[j]; return i; } // vector template ostream &operator<<(ostream &s, const vector &v) { int len = v.size(); for(int i = 0; i < len; ++i) { s< ostream &operator<<(ostream &s, const vector > &vv) { s< &g, ll start, Vec &dist) { priority_queue, function> q([](P a, P b)->ll { return a.second > b.second; }); dist[start] = 0; q.push(mp(start, 0)); while (!q.empty()) { P now = q.top(); q.pop(); if(dist[now.fi] < now.se) continue; Each(nxt, g[now.fi]) { if(chmin(dist[nxt.fi], now.se+nxt.se)) { q.push(mp(nxt.fi, dist[nxt.fi])); } } } } int solve() { ll n; cin>>n; ll k; cin>>k; Vec A(n); VV g(n); rep(i, n) { cin>>A[i]; ll m; cin>>m; rep(j, m) { ll b; cin>>b; b--; g[i].pb(b); } } dbg(g); dbg(A); Vec dp(n+1,-INF); dp[0] = 0; rep(i, n) { chmax(dp[i+1], dp[i]); Each(j, g[i]) { //交換 chmax(dp[i+1], dp[j+1] + A[i]-A[j]); } } ll ans = 0; rep(i,n){ chmax(ans, dp[i+1]); } dbg(dp); out(ans); return 0; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout<>T; // while(T--) solve(); }