#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1010
#define MAXS 20
#define INF 1000000000
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
int A[MAX];
int B[MAX];
int dp[MAX][20010];
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int N, E;
cin >> N >> E;
int i, j;
int U = E - 1;
for (i = 2; i <= N; i++) {
cin >> A[i] >> B[i];
U = max(U, A[i] + B[i]);
}
fill(&dp[0][0], &dp[MAX - 1][MAX], -INF);
for (i = 0; i < E; i++) dp[1][i] = i;
for (i = 2; i <= N; i++) {
int mx = 0;
for (j = 0; j < A[i]; j++) mx = max(mx, dp[i - 1][j]);
for (j = 0; j < B[i]; j++) dp[i][j] = max(dp[i][j], mx + j);
for (j = A[i] + B[i]; j <= U; j++) dp[i][j] = max(dp[i][j], dp[i - 1][j]);
for (j = A[i]; j < A[i] + B[i]; j++) dp[i][j - A[i]] = max(dp[i][j - A[i]], dp[i - 1][j]);
for (j = 0; j < A[i]; j++) dp[i][B[i] + j] = max(dp[i][B[i] + j], dp[i - 1][j] + B[i]);
}
int mx = 0;
for (i = 0; i <= U; i++) mx = max(mx, dp[N][i]);
cout << mx;
}
