// 朴素二维版本
cin >> n >> m;
rep(i, 1, n) cin >> v[i] >> w[i];

rep(i, 1, n) // 枚举物品
{
    rep(j, 0, m) // 枚举容积
    {
        f[i][j] = f[i - 1][j]; // 不选
        if (j >= v[i])         // 选（前提是装得下）
            f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
    }
}
cout << f[n][m] << endl;

// 空间优化核心代码
// v[i]: 体积, w[i]: 价值, s: 背包总容量
vll f(s + 1, 0); 

rep(i, 1, n) // 第一层循环：枚举物品
{
    // 第二层循环：必须倒序！从背包容量 s 遍历到 v[i]
    dep(j, s, v[i])
    {
        f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
}
cout << f[s] << endl;

#include <bits/stdc++.h>
using namespace std;

typedef long long ll; 
typedef vector<ll> vll;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define INF 0x3f3f3f3f3f3f3f3f

const int N = 1e3 + 10;
ll n, m;
ll v[N], w[N];

void solve()
{
    cin >> n >> m;
    rep(i, 1, n) cin >> v[i] >> w[i];
    
    // dp1: 不要求装满，全部初始化为 0
    vll dp1(m + 1, 0);
    
    // dp2: 要求恰好装满，初始化为 -INF，只有 dp2[0] 为 0
    vll dp2(m + 1, -INF);
    dp2[0] = 0;

    rep(i, 1, n)
    {
        dep(j, m, v[i])
        {
            // 方案 1 转移
            dp1[j] = max(dp1[j], dp1[j - v[i]] + w[i]);
            
            // 方案 2 转移 (逻辑完全一样)
            dp2[j] = max(dp2[j], dp2[j - v[i]] + w[i]);
        }
    }

    // 输出方案 1
    cout << dp1[m] << endl;

    // 输出方案 2
    // 注意：如果 dp2[m] 依然是负数（说明由 -INF 转移而来），则无解
    if (dp2[m] < 0)
    {
        cout << 0 << endl;
    }
    else
    {
        cout << dp2[m] << endl;
    }
}

int main()
{
    IOS;
    int _ = 1;
    while (_--)
    {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'

int n;
int arr[15];    // 存储当前的排列结果
bool st[15];    // 状态数组，记录数字是否被使用

// x 表示当前正在枚举第几个位置
void dfs(int x) {
    // 1. 截止条件：如果位置 x 超过了 n，说明 1~n 都填好了
    if (x > n) {
        for (int i = 1; i <= n; i++) {
            // 题目要求保留 5 个场宽
            printf("%5d", arr[i]);
        }
        printf("\n");
        return; // 非常重要！必须返回，否则会越界继续执行
    }

    // 2. 枚举当前位置 x 可以填入的数字 (1 到 n)
    for (int i = 1; i <= n; i++) {
        // 如果数字 i 没有被使用过
        if (!st[i]) {
            
            // 2.1 修改状态（占位）
            arr[x] = i;      // 把 i 填入第 x 个坑
            st[i] = true;    // 标记 i 已经被用过了

            // 2.2 递归到下一层
            dfs(x + 1);

            // 2.3 回溯（恢复现场）
            // 这一步至关重要：从下一层回来后，要把 i 拿出来，
            // 标记为未使用，这样循环到下一次或者回退时才能再次使用 i
            arr[x] = 0;      // (可选) 实际上会被覆盖，不写也没事
            st[i] = false;   // 核心：解除标记
        }
    }
}

void solve() {
    cin >> n;
    dfs(1); // 从第 1 个位置开始搜索
}

int main() {
    // 由于使用了 printf，混合 cin/cout 时最好不要关闭同步流，或者只用 C 风格 IO
    // 这里为了题目要求的格式化输出，核心部分使用了 printf
    int _ = 1;
    while (_--) {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'

int n, r; // n选r
int arr[25]; // 存储当前的组合

// x: 当前枚举到了第几个位置 (1..r)
// start: 当前位置只能填 >= start 的数字
void dfs(int x, int start)
{
    // 1. 截止条件：选够了 r 个数
    if (x > r)
    {
        for (int i = 1; i <= r; i++)
        {
            printf("%3d", arr[i]); // 题目要求3个场宽
        }
        cout << endl;
        return;
    }

    // 2. 枚举当前位置能填的数
    // 只能从 start 开始填，保证单调递增，从而保证是组合而不是排列
    for (int i = start; i <= n; i++)
    {
        arr[x] = i; // 填入数字
        
        // 3. 递归下一层
        // 下一个位置必须从 i+1 开始填
        // 错误示范：dfs(x + 1, start + 1) -> 会导致重复或非递增
        dfs(x + 1, i + 1); 
        
        arr[x] = 0; // 回溯（其实不写也行，会被覆盖）
    }
}

void solve()
{
    cin >> n >> r;
    // 从第 1 个位置开始填，数字最小从 1 开始
    dfs(1, 1);
}

int main()
{
    // IOS; 
    // 注意：混用 printf 和 cout 时建议不要关同步，或者统一用一种 IO
    int _ = 1;
    while (_--)
    {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; 
#define endl '\n'

// 题目参数
ll n;  
// 字典序 N < Y，所以 N 放前面(对应索引0)，Y 放后面(对应索引1)
char op[2]={'N','Y'};
string ans; // 记录当前的决策路径 (充当栈)

// x 表示当前正在做第 x 个人的决定
void dfs(int x){
    // 1. 截止条件：已经做完 n 个人的决定了
    if(x > n){
        cout << ans << endl;
        return ;
    }

    // 2. 枚举当前人的两种状态：0(N) 和 1(Y)
    for(int i = 0; i <= 1; i++){
        ans += op[i];    // 1. 做出选择 (入栈)
        
        dfs(x + 1);      // 2. 递归下一层 (处理下一个人)
        
        ans.pop_back();  // 3. 回溯 (出栈，恢复现场)
    }
}       

void solve()
{
    cin >> n;
    dfs(1); // 从第 1 个人开始
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 1e5 + 10, M = 2 * N, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template <typename T>
struct BIT1
{
    int n;
    vector<T> tr;
    BIT1(int n) : n(n), tr(n + 1) {}
    void add(int x, T v)
    {
        for (; x <= n; x += x & -x)
            tr[x] += v;
    }
    T sum(int x)
    {
        T r = 0;
        for (; x; x -= x & -x)
            r += tr[x];
        return r;
    }
    T range(int l, int r) { return sum(r) - sum(l - 1); }
};
template <typename T>
struct BIT2
{
    int n, m;
    vector<vector<T>> t1, t2, t3, t4;
    BIT2(int n_ = 0, int m_ = 0) { init(n_, m_); }
    void init(int n_, int m_)
    {
        n = n_;
        m = m_;
        t1.assign(n + 1, vector<T>(m + 1, T{}));
        t2.assign(n + 1, vector<T>(m + 1, T{}));
        t3.assign(n + 1, vector<T>(m + 1, T{}));
        t4.assign(n + 1, vector<T>(m + 1, T{}));
    }
    void _add(int x, int y, const T &v)
    {
        for (int i = x; i <= n; i += i & -i)
            for (int j = y; j <= m; j += j & -j)
            {
                t1[i][j] += v;
                t2[i][j] += v * x;
                t3[i][j] += v * y;
                t4[i][j] += v * x * y;
            }
    }
    void rangeAdd(int x1, int y1, int x2, int y2, const T &v)
    {
        _add(x1, y1, v);
        _add(x1, y2 + 1, -v);
        _add(x2 + 1, y1, -v);
        _add(x2 + 1, y2 + 1, v);
    }
    T prefixSum(int x, int y)
    {
        T r{};
        for (int i = x; i > 0; i -= i & -i)
            for (int j = y; j > 0; j -= j & -j)
                r += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
        return r;
    }
    T rangeSum(int x1, int y1, int x2, int y2)
    {
        if (x1 > x2 || y1 > y2)
            return T{};
        return prefixSum(x2, y2) - prefixSum(x1 - 1, y2) - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
    }
};
struct Random
{
    mt19937_64 rng;
    Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
    ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
    ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
    int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
    double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
    bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
    template <typename T>
    void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
    ll res = 1 % p;
    a %= p;
    while (b)
    {
        if (b & 1)
            res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
/*

*/
ll n, m;
ll w[N], v[N];
ll f[1000][1000];
void solve()
{
    cin >> n >> m;
    rep(i, 1, n) cin >> w[i] >> v[i];
    rep(i, 1, n)
    {
        rep(j, 0, m)
        {
            f[i][j] = f[i - 1][j];
            if (j >= w[i])
            {
                f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
            }
        }
    }
    rep(i, 0, n)
    {
        rep(j, 0, m)
        {
            cout << f[i][j] << " ";
        }
        cout << endl;
    }
}

int main()
{
    IOS;

    int _ = 1;
    // cin>>_;//如果是多组数据
    while (_--)
    {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

//CJX__//

typedef long long ll; 
typedef pair<ll, ll> PLL;
typedef vector<ll> vll;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define fi first
#define se second

/*
   分治法求解最大最小值
*/

vll a; 

PLL dfs(int l, int r) {
    if (l == r) return {a[l], a[l]};
    if (l + 1 == r) return {min(a[l], a[r]), max(a[l], a[r])};

    int mid = (l + r) >> 1;
    PLL L = dfs(l, mid);
    PLL R = dfs(mid + 1, r);

    return {min(L.fi, R.fi), max(L.se, R.se)};
}

void solve()
{
    int n;
    cin >> n;
    a.assign(n + 1, 0);
    rep(i, 1, n) cin >> a[i];

    PLL res = dfs(1, n);
    cout << res.se << " " << res.fi << endl; // 输出 最大值 最小值
}

int main()
{
    IOS; 
    int _ = 1;
    while (_--)
    {
        solve();
    }
    return 0;
}

void solve(){
    ll n;
    cin >> n;
    vll a(n + 1, 0), f(n + 1, 0);
    ll ans = -INF;
    rep(i, 1, n) cin >> a[i];
    
    rep(i, 1, n)
    {
        f[i] = max(f[i - 1] + a[i], a[i]);
        cmax(ans, f[i]);
    }

    cout << ans << endl;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
    ll n;
    cin >> n;
    vector<ll> a(n + 1, 0);
    for (ll i = 1; i <= n; i++) cin >> a[i];

    // 分治核心函数
    function<ll(ll, ll)> fz = [&](ll l, ll r) -> ll
    {
        // 1. 递归基：区间长度为1，直接返回
        if (l == r) return a[l];

        ll mid = l + r >> 1;

        // 2. 递归求左右两边的最大子段和
        ll lmax = fz(l, mid);
        ll rmax = fz(mid + 1, r);

        // 3. 求跨越中点的最大子段和
        // 左半部分：从 mid 向左扫描，找最大后缀和
        ll s1 = -INF, sum = 0;
        for (ll i = mid; i >= l; i--) {
            sum += a[i];
            s1 = max(s1, sum);
        }

        // 右半部分：从 mid+1 向右扫描，找最大前缀和
        ll s2 = -INF; sum = 0;
        for (ll i = mid + 1; i <= r; i++) {
            sum += a[i];
            s2 = max(s2, sum);
        }

        // 4. 返回三者最大值
        return max({lmax, rmax, s1 + s2});
    };

    cout << fz(1, n) << endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}