#include <bits/stdc++.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

int main(){
  vector <int> dp(8000);
  rep(i, 8000) dp[i] = 0;
  int N, T; cin >> N >> T;
  vector<pair <int, int>>AB;
  rep(i, N){
    int a, b; cin >> a >> b;
    AB.push_back(make_pair(a, b));
  }
  sort(AB.begin(), AB.end());
  
  rep(i,  N){
    vector <int> temp;
    copy(dp.begin(), dp.end(), back_inserter(temp));
    rep(t, T){
      dp[t + AB[i].first] = max(temp[t + AB[i].first], temp[t] + AB[i].second);
    }
  }
  int ans = *max_element(dp.begin(), dp.end());
  cout << ans <<endl;
}
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
using namespace std;
using ll = int64_t;
using vi = vector<int>;
using vvi = vector<vi>;

vi color;
vvi G;


bool dfs(int v, int c) {
    if(color[v]  != -1) {
        if(c%2 == color[v]) {
            return true;
        } else {
            return false;
        }
    }
    color[v] = c%2;
    for(int next:G[v]){
       if(!dfs(next, c+1)) {
           return false;
       }
    }
    return true;
}

int main() {
    ll N, M;
    scanf("%lld%lld", &N, &M);
    G.resize(N);
    rep(i, M) {
        int a, b;
        scanf("%d%d", &a, &b);
        G[a-1].push_back(b-1);
        G[b-1].push_back(a-1);
    }
    color.assign(N, -1);
    if(!dfs(0, 0)) {
        cout << N*(N-1)/2-M << '\n';
        return 0;
    }
    int cc=0;
    rep(i, N) {
        if(color[i]) {
            ++cc;
        }
    }
    cout << (N-cc)*cc-M << '\n';
}