#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <cstdio>
#include "A+B.h"
//#include <sys/resource.h>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T> void print(deque <T> v);
template <class T> void print(queue <T> q);
template <class T> void print(priority_queue <T> q);
template <class T> void print(int n, T arr[]);
template <class T> void print(stack <T> st);
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(queue <T> q) {cerr << "[ "; while(!q.empty()) {print(q.front()); cerr << " "; q.pop();} cerr << "]";}
template <class T> void print(priority_queue <T> q) {cerr << "[ "; while(!q.empty()) {print(q.top()); cerr << " "; q.pop();} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(int n, T arr[]) {cerr << "[ "; for(int i = 0; i <= n; i++) {print(arr[i]); cerr << " ";} cerr << "]\n";}
template <class T> void print(stack <T> st) {cerr << "[ "; while(!st.empty()) {print(st.top()); st.pop(); cerr << ' ';} cerr << "]\n";}
 
#define pb push_back
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define noAnsw cout << -1 << '\n'
#define ll long long
#define ppb pop_back
#define OK cout << "OK" << endl;
#define ld long double
#define all(v) (v).begin(), (v).end()
#define MP make_pair
#define PII pair <int, int>
#define endl '\n'
#define ull unsigned long long
#define PLL pair <ll, ll>
#define PIL pair <int, ll>
#define PLI pair <ll, int>
#define rall(v) (v).rbegin(), (v).rend() 
#define priora priority_queue
#define urishOK cout << "urishOK\n";
 
void setIO(string name = "") {
	if (!name.empty()) {
		freopen((name + ".in").c_str(), "r", stdin);  
		freopen((name + ".out").c_str(), "w", stdout);
	}
}
void fastIO(){
    ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL); 
}
void setPrecision(int x){
    if(x == 0){
        return;
    }
    cout.setf(ios::fixed);
    cout.precision(x);
    return;
}
 
const int inf = 1e9 + 5, LOG = 21;
const ll inf64 = 1e18 + 5, mod = 1e9 + 7, wmod = 998244353;
const double epsilon = 0.000001, pi = 3.14159265359;

__int128_t find_sum(__int128_t a, __int128_t b){
    return a + b;
}
 
// const int N = 105, M = 1e4 + 5;
// int n, max_sum[N][N], m, dp[N][M];
// vector <int> a[N], pref, suff;

// void solve(int TST_NUM){
//     cin >> n >> m;
//     for(int i = 1; i <= n; i++){
//         int len;
//         cin >> len;
//         a[i].resize(len + 1);
//         pref.assign(len + 1, 0);
//         suff.assign(len + 2, 0);
//         for(int j = 1; j <= len; j++){
//             cin >> a[i][j];
//         }
//         for(int j = 1; j <= len; j++) pref[j] = pref[j - 1] + a[i][j];
//         for(int j = len; j >= 1; j--) suff[j] = suff[j + 1] + a[i][j];

//         // dbg(pref);
//         // dbg(suff);
//         for(int l = 1; l <= len; l++){
//             //max_sum[i][l] = suff[len - l + 1];
//             for(int j = 0; j <= len; j++){
//                 int t = len - (l - j) + 1;
//                 if(t <= j || t > len + 1) continue;
//                 // dbg(MP(j, t));
//                 // dbg(pref[j] + suff[t]);
//                 max_sum[i][l] = max(max_sum[i][l], pref[j] + suff[t]);
//                 // dbg(MP(len, j));
//                 // dbg(max_sum[i][l]);
//             }
//         }
//         // for(int j = 1; j <= len ;j++){
//         //     cout << max_sum[i][j] << ' ';
//         // }
//         // cout << endl;
//     }

//     dp[0][0] = 0;
//     for(int i = 1; i <= n; i++){
//         for(int j = 0; j <= m; j++){
//             for(int t = 0; t <= a[i].size(); t++){
//                 //update dp[i][j] via dp[i - 1][j - t]
//                 if(j >= t) dp[i][j] = max(dp[i][j], dp[i - 1][j - t] + max_sum[i][t]);
//             }
//         }
//     }

//     // for(int i = 1; i <= n; i++){
//     //     for(int j = 0; j <= m; j++){
//     //         cout << "dp[" << i << "][" << j << "] = " << dp[i][j] << endl;
//     //     }
//     // }

//     cout << dp[n][m] << endl;
// }  
 
// int main(){
//     setPrecision(1);
//     fastIO();
//     //increaseStack(64 * 1024 * 1024);
//     //setIO("file");
 
//     int Tests = 1;
//     //cin >> Tests;
 
//     int TST_NUM = 1;
//     while(Tests--){
//         solve(TST_NUM++);
//     }
//     return 0; 
// } 
// //mcmcmcmcmcmcmcmcmcmcmc
// //mcmcmcmcmcmcmcmcmcmcmc
// //mcmcmcmcmcmcmcmcmcmcmc
// //mcmcmcmcmcmcmcmcmcmcmc
// //matsak
