Vasya got really tired of these credits (from problem F) and now wants to earn the money himself! He decided to make a contest to gain a profit.

Vasya has n problems to choose from. They are numbered from 1 to n. The difficulty of the i-th problem is d_i. Moreover, the problems are given in the increasing order by their difficulties. The difficulties of all tasks are pairwise distinct. In order to add the i-th problem to the contest you need to pay c_i burles to its author. For each problem in the contest Vasya gets a burles.

In order to create a contest he needs to choose a consecutive subsegment of tasks.

So the total earnings for the contest are calculated as follows: 

  * if Vasya takes problem i to the contest, he needs to pay c_i to its author; 
  * for each problem in the contest Vasya gets a burles; 
  * let gap(l, r) = max_{l ≤ i < r} (d_{i + 1} - d_i)^2. If Vasya takes all the tasks with indices from l to r to the contest, he also needs to pay gap(l, r). If l = r then gap(l, r) = 0. 



Calculate the maximum profit that Vasya can earn by taking a consecutive segment of tasks.

Input

The first line contains two integers n and a (1 ≤ n ≤ 3 ⋅ 10^5, 1 ≤ a ≤ 10^9) — the number of proposed tasks and the profit for a single problem, respectively.

Each of the next n lines contains two integers d_i and c_i (1 ≤ d_i, c_i ≤ 10^9, d_i < d_{i+1}).

Output

Print one integer — maximum amount of burles Vasya can earn.

Examples

Input


5 10
1 15
5 3
6 11
7 2
11 22


Output


13


Input


3 5
1 8
2 19
3 11


Output


0
#include <bits/stdc++.h>
using namespace std;
template <typename T>
class SegTree {
 private:
  const T min_int;
  vector<T>& vals;
  vector<T> maxs;
  vector<T> pending;
  void _build(int n, int s, int e) {
    if (s == e) {
      maxs[n] = vals[s];
      return;
    }
    int mid = (s + e) / 2;
    _build(2 * n, s, mid);
    _build(2 * n + 1, mid + 1, e);
    maxs[n] = max(maxs[2 * n], maxs[2 * n + 1]);
  }
  void _propagate(int n, int s, int e) {
    if (pending[n] != 0) {
      maxs[n] += pending[n];
      if (s != e) {
        pending[2 * n] += pending[n];
        pending[2 * n + 1] += pending[n];
      }
      pending[n] = 0;
    }
  }
  void _update_range(int n, int s, int e, int a, int b, T delta) {
    _propagate(n, s, e);
    if (a > e || b < s) {
      return;
    }
    if (a <= s && e <= b) {
      maxs[n] += delta;
      if (s != e) {
        pending[2 * n] += delta;
        pending[2 * n + 1] += delta;
      }
      return;
    }
    int mid = (s + e) / 2;
    _update_range(2 * n, s, mid, a, b, delta);
    _update_range(2 * n + 1, mid + 1, e, a, b, delta);
    maxs[n] = max(maxs[2 * n], maxs[2 * n + 1]);
  }
  T _query(int n, int s, int e, int a, int b) {
    if (a > e || b < s) {
      return min_int;
    }
    _propagate(n, s, e);
    if (a <= s && e <= b) {
      return maxs[n];
    }
    int mid = (s + e) / 2;
    T left = _query(2 * n, s, mid, a, b);
    T right = _query(2 * n + 1, mid + 1, e, a, b);
    return max(left, right);
  }

 public:
  SegTree(vector<T>& values) : vals(values), min_int(numeric_limits<T>::min()) {
    maxs.resize(4 * vals.size());
    pending.resize(4 * vals.size());
    _build(1, 0, vals.size() - 1);
  }
  void update_range(int a, int b, T delta) {
    _update_range(1, 0, vals.size() - 1, a, b, delta);
  }
  int query(int a, int b) {
    if (a == b) {
      return 0;
    }
    return _query(1, 0, vals.size() - 1, a + 1, b);
  }
};
template <typename T>
class ContrSegTree {
 private:
  const T min_int;
  vector<T>& vals;
  vector<T> maxs;
  vector<T> pending;
  void _build(int n, int s, int e) {
    if (s == e) {
      maxs[n] = vals[s] - (s > 0 ? vals[s - 1] : 0);
      return;
    }
    int mid = (s + e) / 2;
    _build(2 * n, s, mid);
    _build(2 * n + 1, mid + 1, e);
    T total_contr = vals[e] - (s > 0 ? vals[s - 1] : 0);
    maxs[n] = max(total_contr, max(maxs[2 * n], maxs[2 * n + 1]));
  }
  T _query(int n, int s, int e, int a, int b) {
    if (a > e || b < s) {
      return min_int;
    }
    if (a <= s && e <= b) {
      return maxs[n];
    }
    int mid = (s + e) / 2;
    T left = _query(2 * n, s, mid, a, b);
    T right = _query(2 * n + 1, mid + 1, e, a, b);
    T total_contr = vals[e] - (s > 0 ? vals[s - 1] : 0);
    return max(total_contr, max(left, right));
  }

 public:
  ContrSegTree(vector<T>& values)
      : vals(values), min_int(numeric_limits<T>::min()) {
    maxs.resize(4 * vals.size());
    pending.resize(4 * vals.size());
    _build(1, 0, vals.size() - 1);
  }
  int query(int a, int b) { return _query(1, 0, vals.size() - 1, a, b); }
};
long long solve(int s, int e, vector<long long>& contr,
                SegTree<long long>& max_diff,
                ContrSegTree<long long>& max_contr) {
  if (e - s == 0) {
    return contr[s] - (s > 0 ? contr[s - 1] : 0);
  }
  int mid = (s + e) / 2;
  long long left = solve(s, mid, contr, max_diff, max_contr);
  long long right = solve(mid + 1, e, contr, max_diff, max_contr);
  long long best_right = numeric_limits<long long>::min();
  long long best_right_max = 0;
  int best_right_i = 0;
  for (int i = mid; i <= e; i++) {
    long long max_seg = max_diff.query(mid, i);
    long long cur =
        contr[i] - (mid > 0 ? contr[mid - 1] : 0) - max_seg * max_seg;
    if (cur >= best_right) {
      best_right = cur;
      best_right_max = max_seg;
      best_right_i = i;
    }
  }
  long long best_left = numeric_limits<long long>::min();
  long long best_left_max = 0;
  int best_left_i = 0;
  for (int i = mid; i >= s; i--) {
    long long max_seg = max_diff.query(i, mid);
    long long cur = contr[mid] - (i > 0 ? contr[i - 1] : 0) - max_seg * max_seg;
    if (cur >= best_left) {
      best_left = cur;
      best_left_max = max_seg;
      best_left_i = i;
    }
  }
  long long max_crossing = max(best_left_max, best_right_max);
  long long mid_contr = contr[mid] - (mid > 0 ? contr[mid - 1] : 0);
  long long best_crossing =
      best_right + best_left + best_left_max * best_left_max +
      best_right_max * best_right_max - max_crossing * max_crossing - mid_contr;
  return max(best_crossing, max(left, right));
}
int main() {
  ios::sync_with_stdio(false);
  long long N, K;
  cin >> N >> K;
  vector<long long> D(N);
  vector<long long> diff(N);
  vector<long long> C(N);
  vector<long long> contr(N);
  for (int i = 0; i < N; i++) {
    cin >> D[i] >> C[i];
    diff[i] = D[i] - (i > 0 ? D[i - 1] : 0);
    contr[i] = K - C[i] + (i > 0 ? contr[i - 1] : 0);
  }
  SegTree<long long> max_diff(diff);
  ContrSegTree<long long> max_contr(contr);
  cout << max(0ll, solve(0, N - 1, contr, max_diff, max_contr)) << endl;
  return 0;
}
