#include <iostream>
#include <iomanip>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <tuple>
#include <math.h>
#include <set>
#include <map>
using namespace std ;
using ll = long long ;
using ld = long double ;
using vll = vector<ll> ;
using vvll = vector<vll> ;
using vc = vector<char> ;
using vvc = vector<vc> ;
using vb = vector<bool> ;
using vvb = vector<vb> ;
using pll = pair<ll,ll> ;
#define all(v) v.begin(),v.end() 
const ll INF = 1e18 ;
const ll mod = 1e9+7 ;
const double pie = acos(-1); 
vll dx4 = {-1,0,1,0} ;
vll dy4 = {0,-1,0,1} ;
vll dx8 = {-1,0,1,1,1,0,-1,-1} ;
vll dy8 = {-1,-1,-1,0,1,1,1,0} ; 

void fix_cout(){cout << fixed << setprecision(20) ; }
ll gcd(ll a,ll b){if(b==0) return a ; return gcd(b,a%b) ; }
ll lcm(ll a,ll b){return a/gcd(a,b)*b ; }
void chmax(ll &a,ll b){if(a<b) a = b ; }
void chmin(ll &a,ll b){if(a>b) a = b ; }

int main(){
	ll h,w ;
	cin >> h >> w ;
	map<ll,ll> gs,dis ;
	for(int i=1;i<=w;i++) gs[i] = i ;
	gs[w+10] = -1 ;
	dis[0] = w ;
	for(int i=1;i<=h;i++){
		ll a,b ;
		cin >> a >> b ;
		ll mx = -1 ;
		for(auto it=gs.lower_bound(a);it->first<=b+1;it=gs.erase(it)){
			ll g = it->first ;
			ll s = it->second ;
			chmax(mx,s) ;
			if(dis.count(g-s)){
				dis[g-s]-- ;
				if(dis[g-s]==0) dis.erase(g-s) ;
			}
		}
		if(mx>=0&&b<w){
			gs[b+1] = mx ;
			dis[b+1-mx]++ ;
		}
		ll ans = -1 ;
		if(!dis.empty()){
			ans = i+dis.begin()->first ;
		}
		cout << ans << endl ;
	}
}

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstdio>

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define P pair<int, int>

typedef vector<int> vec;
typedef vector<vec> mat;

int main(){
    int n, K;
    cin >> n >> K;
    int v[n];
    rep(i, n) cin >> v[i];
    int mx = min(n, K);
    int ans = 0;
    for (int i = 0; i <= mx; i++){
        for (int j = 0; j <= i; j++){
            vec v_s;
            for (int k = 0; k < j; k++){
                v_s.push_back(v[k]);
            }
            for (int k = n - 1; k > (n - 1) - (i - j); k--){
                v_s.push_back(v[k]);
            }
            sort(v_s.begin(), v_s.end());
            // for (int k = 0; k < v_s.size(); k++){
            //     cout << v_s[k] << " ";
            // }cout << endl;
            
            int sm = 0;
            rep(k, v_s.size()){
                if(k < K - i && v_s[k] < 0) continue;
                sm += v_s[k];
            }
            // cout << sm << endl;
            ans = max(sm, ans);
        }
    }
    cout << ans << endl;
}