#include <bits/stdc++.h>

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                              \
  do {                                        \
    cerr << #__VA_ARGS__ << ": ";             \
    debug(__VA_ARGS__);                       \
    cerr << " (L" << __LINE__ << ")" << endl; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define in(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << std::endl;
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define out(...) write_to_cout(__VA_ARGS__);

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

using ll = long long;

using namespace std;

int main() {
  in(int, n, t);
  vector<pair<int, int>> f(n);
  rep(i, n) cin >> f[i].first >> f[i].second;
  sort(all(f));
  vector<int> dp(t + 3001);
  int ans = 0;
  rep(i, n) {
    for (int j = t - 1; j >= 0; --j) {
      dp[j + f[i].first] = max(dp[j + f[i].first], dp[j] + f[i].second);
      ans = max(ans, dp[j + f[i].first]);
    }
  }
  out(ans);
}

#include<bits/stdc++.h>

using namespace std;

const int N = 123456;

int n, m, color[N];
vector<int> adj[N];
bool visit[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1, x, y; i <= m; ++i) {
    cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  int a = 0, b = 0, c = 0, number;
  bool ok;
  for (int i = 1; i <= n; ++i) {
    if (!visit[i]) {
      function<void (int, int)> dfs = [&] (int x, int z) {
        ++number;
        visit[x] = true;
        color[x] = z;
        for (auto y : adj[x]) {
          if (!visit[y]) {
            dfs(y, !z);
          } else if (color[y] != (!z)) {
            ok = false;
          }
        }
      };
      number = 0;
      ok = true;
      dfs(i, 0);
      if (number == 1) {
        ++a;
      } else if (!ok) {
        ++b;
      } else {
        ++c;
      }
    }
  }
  long long answer = 0;
  answer += (long long) a * a;
  answer += (long long) a * (n - a) << 1;
  answer += (long long) b * b;
  answer += (long long) b * c << 1;
  answer += (long long) c * c << 1;
  cout << answer << '\n';
  return 0;
}