There are n cities in the country where the Old Peykan lives. These cities are located on a straight line, we'll denote them from left to right as c1, c2, ..., cn. The Old Peykan wants to travel from city c1 to cn using roads. There are (n - 1) one way roads, the i-th road goes from city ci to city ci + 1 and is di kilometers long.

The Old Peykan travels 1 kilometer in 1 hour and consumes 1 liter of fuel during this time.

Each city ci (except for the last city cn) has a supply of si liters of fuel which immediately transfers to the Old Peykan if it passes the city or stays in it. This supply refreshes instantly k hours after it transfers. The Old Peykan can stay in a city for a while and fill its fuel tank many times. 

Initially (at time zero) the Old Peykan is at city c1 and s1 liters of fuel is transferred to it's empty tank from c1's supply. The Old Peykan's fuel tank capacity is unlimited. Old Peykan can not continue its travel if its tank is emptied strictly between two cities.

Find the minimum time the Old Peykan needs to reach city cn.

Input

The first line of the input contains two space-separated integers m and k (1 ≤ m, k ≤ 1000). The value m specifies the number of roads between cities which is equal to n - 1.

The next line contains m space-separated integers d1, d2, ..., dm (1 ≤ di ≤ 1000) and the following line contains m space-separated integers s1, s2, ..., sm (1 ≤ si ≤ 1000).

Output

In the only line of the output print a single integer — the minimum time required for The Old Peykan to reach city cn from city c1.

Examples

Input

4 6
1 2 5 2
2 3 3 4


Output

10


Input

2 3
5 6
5 5


Output

14

Note

In the second sample above, the Old Peykan stays in c1 for 3 hours.
#include <bits/stdc++.h>
using namespace std;
unsigned long long determine_output(unsigned long long num_roads,
                                    unsigned long long refresh_time);
char *substring(unsigned long long start, unsigned long long end, char *str);
char *lower(char *str);
unsigned long long contains_word(char *container_str, char *word_str);
unsigned long long abs_val(unsigned long long num);
unsigned long long is_prime(unsigned long long num);
double degrees_to_radians(unsigned long long angle);
deque<unsigned long long> d_deque;
deque<unsigned long long> s_deque;
int main() {
  unsigned long long m, k, i, d_i, s_i;
  cin >> m;
  cin >> k;
  for (i = 0; i < m; i++) {
    cin >> d_i;
    d_deque.push_back(d_i);
  }
  for (i = 0; i < m; i++) {
    cin >> s_i;
    s_deque.push_back(s_i);
  }
  cout << determine_output(m, k) << endl;
}
unsigned long long determine_output(unsigned long long num_roads,
                                    unsigned long long refresh_time) {
  bool debug = false;
  unsigned long long d[d_deque.size()];
  unsigned long long s[s_deque.size()];
  int i;
  for (i = 0; i < num_roads; i++) {
    d[i] = d_deque.front();
    s[i] = s_deque.front();
    d_deque.pop_front();
    s_deque.pop_front();
  }
  unsigned long long max_i = 0;
  unsigned long long max_fuel = s[0];
  unsigned long long total_time = 0;
  unsigned long long fuel_left = s[0];
  unsigned long long d_next, s_next;
  unsigned long long d_curr = d[0];
  unsigned long long s_curr = s[0];
  if (debug) {
    cout << "Start at city index 0\n";
    cout << "\tfuel left = " << fuel_left << endl;
    cout << "\tdistance to next city = " << d_curr << endl << endl;
  }
  for (i = 1; i < num_roads; i++) {
    d_next = d[i];
    s_next = s[i];
    if (d_curr > fuel_left) {
      if (debug)
        cout << "Not enough fuel; stop at city index " << max_i
             << " to refresh fuel\n";
    } else if (debug)
      cout << "There is enough fuel to move on\n";
    while (d_curr > fuel_left) {
      fuel_left += max_fuel;
      total_time += refresh_time;
      if (debug) cout << "\ttotal fuel left is now " << fuel_left << endl;
    }
    if (debug) cout << "\nMoved on to city index " << i << endl;
    fuel_left -= d_curr;
    total_time += d_curr;
    if (debug) cout << "\tfuel left = " << fuel_left << endl << endl;
    fuel_left += s_next;
    if (s_next > max_fuel) {
      max_fuel = s_next;
      max_i = i;
    }
    d_curr = d[i];
    s_curr = s[i];
    if (debug) {
      cout << "Refreshed fuel\n";
      cout << "\tfuel left = " << fuel_left << endl;
      cout << "\tdistance to next city = " << d_curr << endl << endl;
    }
  }
  if (d_curr > fuel_left) {
    if (debug)
      cout << "Not enough fuel; stop at city index " << max_i
           << " to refresh fuel\n";
  } else if (debug)
    cout << "There is enough fuel to move on\n";
  while (d_curr > fuel_left) {
    fuel_left += max_fuel;
    total_time += refresh_time;
    if (debug) cout << "\tfuel left is now " << fuel_left << endl;
  }
  total_time += d_curr;
  fuel_left -= d_curr;
  if (debug) {
    cout << "\nMoved on to the last city\n";
    cout << "\tfuel left = " << fuel_left << endl;
  }
  return total_time;
}
char *substring(unsigned long long start, unsigned long long end, char *str) {
  char *buf = (char *)malloc(sizeof(char) * end + 1 - start);
  strncpy(buf, str + start, end - start);
  buf[end - start] = '\0';
  return buf;
}
char *lower(char *str) {
  char *buf = (char *)malloc(sizeof(char) * strlen(str));
  unsigned long long i;
  for (i = 0; str[i]; i++) buf[i] = tolower(str[i]);
  return buf;
}
unsigned long long contains_word(char *container_str, char *word_str) {
  unsigned long long container_len = strlen(container_str);
  unsigned long long word_len = strlen(word_str);
  unsigned long long flag = 0;
  unsigned long long i, j;
  for (i = 0; i < container_len; i++) {
    for (j = i; j < container_len; j++) {
      if (j == i + word_len) {
        if (strcmp(lower(substring(i, j, container_str)), word_str) == 0)
          flag = 1;
      }
    }
  }
  return flag;
}
unsigned long long abs_val(unsigned long long num) {
  if (num < 0)
    return -num;
  else
    return num;
}
unsigned long long is_prime(unsigned long long num) {
  if (num == 1)
    return false;
  else if (num == 2)
    return true;
  else if (num == 3)
    return true;
  else if (num % 2 == 0)
    return 0;
  else if (num % 3 == 0)
    return 0;
  else {
    unsigned long long i = 5;
    unsigned long long w = 2;
    while (i * i <= num) {
      if (num % i == 0) return false;
      i += w;
      w = 6 - w;
    }
    return true;
  }
}
double degrees_to_radians(unsigned long long angle) {
  double pi = 2 * acos(0);
  return (double)angle * pi / 180.0;
}
