Ordering T-Shirts

It’s another Startup, and that means there are T-shirts to order. In order to make sure T-shirts are shipped as soon as possible, we’ve decided that this year we’re going to order all of the necessary T-shirts before the actual competition. The top C contestants are going to be awarded T-shirts, but we obviously don’t know which contestants that will be. The plan is to get the T-Shirt sizes of all contestants before the actual competition, and then order enough T-shirts so that no matter who is in the top C we’ll have T-shirts available in order to award them.

In order to get the T-shirt sizes of the contestants, we will send out a survey. The survey will allow contestants to either specify a single desired T-shirt size, or two adjacent T-shirt sizes. If a contestant specifies two sizes, it means that they can be awarded either size.

As you can probably tell, this plan could require ordering a lot of unnecessary T-shirts. We’d like your help to determine the minimum number of T-shirts we’ll need to order to ensure that we’ll be able to award T-shirts no matter the outcome of the competition.

Input

Input will begin with two integers N and C (1 ≤ N ≤ 2·10⁵, 1 ≤ C), the number of T-shirt sizes and number of T-shirts to be awarded, respectively.

Following this is a line with 2·N - 1 integers, s ₁ through s _2·N - 1 (0 ≤ s _i ≤ 10⁸). For odd i, s _i indicates the number of contestants desiring T-shirt size ((i + 1) / 2). For even i, s _i indicates the number of contestants okay receiving either of T-shirt sizes (i / 2) and (i / 2 + 1). C will not exceed the total number of contestants.

Output

Print the minimum number of T-shirts we need to buy.

Examples

input

2 200
100 250 100

output

200

input

4 160
88 69 62 29 58 52 44

output

314

Note

In the first example, we can buy 100 of each size.

Solution:

#include <bits/stdc++.h>

using namespace std;

const int N = 1234567;
const long long inf = (long long) 1e18;

long long ma[N], ml[N], mr[N];
int a[N];
long long s[N], f[N];

void modify(int q, long long v) {
ma[q] = max(ma[q], v);
int x = q;
while (x < N) {
    ml[x] = max(ml[x], v);
    x |= (x + 1);
  }
  x = q;
  while (x >= 0) {
mr[x] = max(mr[x], v);
x = (x & (x + 1)) - 1;
}
}

long long get(int ll, int rr) {
long long v = -inf;
int x = ll;
while ((x | (x + 1)) <= rr) {
    v = max(v, mr[x]);
    x |= (x + 1);
  }
  v = max(v, ma[x]);
  x = rr;
  while ((x & (x + 1)) - 1 >= ll) {
v = max(v, ml[x]);
x = (x & (x + 1)) - 1;
}
return v;
}

int main() {
int n;
long long c;
cin >> n >> c;
for (int i = 0; i < 2 * n - 1; i++) {
    scanf("%d", a + i);
  }
  s[0] = 0;
  for (int i = 0; i < 2 * n - 1; i++) {
    s[i + 1] = s[i] + a[i];
  }
  for (int i = 0; i < N; i++) {
    ma[i] = ml[i] = mr[i] = -inf;
  }
  f[0] = 0;
  modify(0, 0);
  for (int i = 1; i <= n; i++) {
    int low = 0, high = i;
    while (low < high) {
      int mid = (low + high) >> 1;
if (s[2 * i - 1] - s[2 * mid] < c) {
        high = mid;
      } else {
        low = mid + 1;
      }
    }
    f[i] = -inf;
    if (low > 0) {
f[i] = max(f[i], c + f[low - 1]);
}
if (low < i) {
      f[i] = max(f[i], s[2 * i - 1] + get(low, i - 1));
    }
    modify(i, f[i] - s[2 * i]);
  }
  cout << f[n] << endl;
  return 0;
}