#include <bits/stdc++.h>
using namespace std;
template <typename T>
using COUPLE = array<T, 2>;
template <typename T>
using TRIPLE = array<T, 3>;
template <typename T>
using QUAD = array<T, 4>;
using Byte = uint8_t;
using LLD = int64_t;
using ULLD = uint64_t;
using UINT = uint32_t;
using PII = pair<int, int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VPII = vector<PII>;
using MII = map<int, int>;
using SI = set<int>;
using VVP = vector<VPII>;
using PLLD = pair<LLD, LLD>;
using VLLD = vector<LLD>;
using VVLLD = vector<VLLD>;
using VPLLD = vector<PLLD>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VCh = vector<char>;
using VVCh = vector<VCh>;
using CI = COUPLE<int>;
using TI = TRIPLE<int>;
using QI = QUAD<int>;
using VCI = vector<CI>;
using VTI = vector<TI>;
using VQI = vector<QI>;
const VPII dirs = {{-1, 0}, {1, 0}, {0, -1}, {-1, 0}};
const int INF = 2147483647 / 2;
const LLD LLDINF = INT64_MAX / 2;
template <typename T>
void dedup(vector<T> &s) {
  sort((s).begin(), (s).end());
  s.erase(unique((s).begin(), (s).end()), s.end());
}
template <int D, typename T>
struct Vecnd : public vector<Vecnd<D - 1, T>> {
  template <typename... Args>
  Vecnd(int n, Args... args)
      : vector<Vecnd<D - 1, T>>(n, Vecnd<D - 1, T>(args...)) {}
};
template <typename T>
struct Vecnd<1, T> : public vector<T> {
  Vecnd(int n, const T &val = T()) : vector<T>(n, val) {}
};
template <typename T>
using Vec1d = Vecnd<1, T>;
template <typename T>
using Vec2d = Vecnd<2, T>;
template <typename T>
using Vec3d = Vecnd<3, T>;
template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
template <typename T>
auto is_streamable(T *ptr) -> decltype(cout << *ptr, 0);
template <typename T>
char is_streamable(...);
struct debug {
  ~debug() {}
  template <typename T>
  typename enable_if<sizeof(is_streamable<T>(0)) != 1, debug &>::type
  operator<<(const T &v) {
    return cout << v, *this;
  }
  template <typename T>
  typename enable_if<sizeof(is_streamable<T>(0)) == 1, debug &>::type
  operator<<(const T &v) {
    *this << "[";
    for (auto it = v.begin(); it != v.end(); ++it) {
      *this << *it;
      if (next(it) != v.end()) *this << ", ";
    }
    return *this << "]";
  }
  template <typename K, typename V>
  debug &operator<<(const pair<K, V> &p) {
    return *this << "(" << p.first << ", " << p.second << ")";
  }
  template <typename T, typename... Args>
  void write(const T &head, const Args &...tail) {
    *this << head << " ", write(tail...);
  }
  void write() { cout << endl; }
};
template <typename T>
auto has_size(T *ptr) -> decltype(ptr->size(), 0);
template <typename T>
char has_size(...);
template <typename T>
typename enable_if<sizeof(has_size<T>(0)) != 1, int>::type operator~(
    const T &container) {
  return (int)container.size();
}
int log2_floor(uint32_t n) { return 31 - __builtin_clz(n); }
int log2_ceil(uint32_t n) { return log2_floor(n) + !!(n & (n - 1)); }
class Rng {
  mt19937 mtgen;
  uniform_int_distribution<int> dist_;

 public:
  Rng(int min, int max, size_t seed = random_device()())
      : mtgen(seed), dist_(min, max) {}
  int operator()() { return dist_(mtgen); }
};
template <typename T>
void pmat_impl(const T &v) {
  int h = v.size(), w = v[0].size(), z = 3;
  for (int i = 0; i < h; ++i) {
    w = max(w, (int)v[i].size());
  }
  cout << "\n" << setw(z) << "+";
  for (int j = 0; j < w; ++j) cout << setw(z) << j << " \n"[j == (w - 1)];
  for (int i = 0; i < h; ++i) {
    cout << setw(z) << i;
    for (int j = 0; j < v[i].size(); ++j)
      cout << setw(z) << v[i][j] << " \n"[j == (v[i].size() - 1)];
  }
  cout << "\n";
}
template <typename... Args>
string fmt(const string &format, const Args &...args) {
  size_t size = snprintf(nullptr, 0, format.c_str(), args...) + 1;
  if (size <= 0) {
    throw runtime_error("Error during formatting.");
  }
  unique_ptr<char[]> buf(new char[size]);
  snprintf(buf.get(), size, format.c_str(), args...);
  return string(buf.get(), buf.get() + size - 1);
}
void writesln() { cout << endl; }
template <typename T, typename... Args>
void writesln(const T &head, const Args &...tail) {
  debug() << head << " ";
  writesln(tail...);
}
template <typename T>
void read(T &x) {
  cin >> x;
}
template <typename T, typename... Args>
void read(T &head, Args &...tail) {
  read(head), read(tail...);
}
void soln(int64_t __ntc, int64_t __tc) {
  int64_t n;
  cin >> n;
  vector<int64_t> pubsize(n), costs(n);
  map<int64_t, multiset<int64_t>> M;
  for (int64_t i = 0; i < n; ++i) {
    cin >> pubsize[i];
  }
  for (int64_t i = 0; i < n; ++i) {
    cin >> costs[i];
    M[pubsize[i]].insert(costs[i]);
  }
  int64_t s = 0;
  multiset<int64_t> C;
  int64_t sig = 0;
  int64_t tot = 0;
  while (true) {
    9;
    ;
    9;
    ;
    if (C.empty()) {
      assert(sig == 0);
      if (M.empty()) break;
      s = M.begin()->first;
      C = M.begin()->second;
      M.erase(M.begin());
      for (auto &i : C) sig += i;
    } else {
      tot += sig - *C.rbegin();
      sig -= *C.rbegin();
      C.erase(prev(C.end()));
      s += 1;
      auto it = M.find(s);
      if (it != M.end()) {
        for (auto &i : it->second) {
          C.insert(i);
          sig += i;
        }
        M.erase(s);
      }
    }
  }
  cout << tot << endl;
}
int64_t Solver() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  soln(1, 1);
  return 0;
}
signed main() { Solver(); }

### Prompt

Develop a solution in Cpp to the problem described below:

VK news recommendation system daily selects interesting publications of one of n disjoint categories for each user. Each publication belongs to exactly one category. For each category i batch algorithm selects a_i publications.

The latest A/B test suggests that users are reading recommended publications more actively if each category has a different number of publications within daily recommendations. The targeted algorithm can find a single interesting publication of i-th category within t_i seconds. 

What is the minimum total time necessary to add publications to the result of batch algorithm execution, so all categories have a different number of publications? You can't remove publications recommended by the batch algorithm.

Input

The first line of input consists of single integer n — the number of news categories (1 ≤ n ≤ 200 000).

The second line of input consists of n integers a_i — the number of publications of i-th category selected by the batch algorithm (1 ≤ a_i ≤ 10^9).

The third line of input consists of n integers t_i — time it takes for targeted algorithm to find one new publication of category i (1 ≤ t_i ≤ 10^5).

Output

Print one integer — the minimal required time for the targeted algorithm to get rid of categories with the same size.

Examples

Input


5
3 7 9 7 8
5 2 5 7 5


Output


6


Input


5
1 2 3 4 5
1 1 1 1 1


Output


0

Note

In the first example, it is possible to find three publications of the second type, which will take 6 seconds.

In the second example, all news categories contain a different number of publications.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using COUPLE = array<T, 2>;
template <typename T>
using TRIPLE = array<T, 3>;
template <typename T>
using QUAD = array<T, 4>;
using Byte = uint8_t;
using LLD = int64_t;
using ULLD = uint64_t;
using UINT = uint32_t;
using PII = pair<int, int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VPII = vector<PII>;
using MII = map<int, int>;
using SI = set<int>;
using VVP = vector<VPII>;
using PLLD = pair<LLD, LLD>;
using VLLD = vector<LLD>;
using VVLLD = vector<VLLD>;
using VPLLD = vector<PLLD>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VCh = vector<char>;
using VVCh = vector<VCh>;
using CI = COUPLE<int>;
using TI = TRIPLE<int>;
using QI = QUAD<int>;
using VCI = vector<CI>;
using VTI = vector<TI>;
using VQI = vector<QI>;
const VPII dirs = {{-1, 0}, {1, 0}, {0, -1}, {-1, 0}};
const int INF = 2147483647 / 2;
const LLD LLDINF = INT64_MAX / 2;
template <typename T>
void dedup(vector<T> &s) {
  sort((s).begin(), (s).end());
  s.erase(unique((s).begin(), (s).end()), s.end());
}
template <int D, typename T>
struct Vecnd : public vector<Vecnd<D - 1, T>> {
  template <typename... Args>
  Vecnd(int n, Args... args)
      : vector<Vecnd<D - 1, T>>(n, Vecnd<D - 1, T>(args...)) {}
};
template <typename T>
struct Vecnd<1, T> : public vector<T> {
  Vecnd(int n, const T &val = T()) : vector<T>(n, val) {}
};
template <typename T>
using Vec1d = Vecnd<1, T>;
template <typename T>
using Vec2d = Vecnd<2, T>;
template <typename T>
using Vec3d = Vecnd<3, T>;
template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
template <typename T>
auto is_streamable(T *ptr) -> decltype(cout << *ptr, 0);
template <typename T>
char is_streamable(...);
struct debug {
  ~debug() {}
  template <typename T>
  typename enable_if<sizeof(is_streamable<T>(0)) != 1, debug &>::type
  operator<<(const T &v) {
    return cout << v, *this;
  }
  template <typename T>
  typename enable_if<sizeof(is_streamable<T>(0)) == 1, debug &>::type
  operator<<(const T &v) {
    *this << "[";
    for (auto it = v.begin(); it != v.end(); ++it) {
      *this << *it;
      if (next(it) != v.end()) *this << ", ";
    }
    return *this << "]";
  }
  template <typename K, typename V>
  debug &operator<<(const pair<K, V> &p) {
    return *this << "(" << p.first << ", " << p.second << ")";
  }
  template <typename T, typename... Args>
  void write(const T &head, const Args &...tail) {
    *this << head << " ", write(tail...);
  }
  void write() { cout << endl; }
};
template <typename T>
auto has_size(T *ptr) -> decltype(ptr->size(), 0);
template <typename T>
char has_size(...);
template <typename T>
typename enable_if<sizeof(has_size<T>(0)) != 1, int>::type operator~(
    const T &container) {
  return (int)container.size();
}
int log2_floor(uint32_t n) { return 31 - __builtin_clz(n); }
int log2_ceil(uint32_t n) { return log2_floor(n) + !!(n & (n - 1)); }
class Rng {
  mt19937 mtgen;
  uniform_int_distribution<int> dist_;

 public:
  Rng(int min, int max, size_t seed = random_device()())
      : mtgen(seed), dist_(min, max) {}
  int operator()() { return dist_(mtgen); }
};
template <typename T>
void pmat_impl(const T &v) {
  int h = v.size(), w = v[0].size(), z = 3;
  for (int i = 0; i < h; ++i) {
    w = max(w, (int)v[i].size());
  }
  cout << "\n" << setw(z) << "+";
  for (int j = 0; j < w; ++j) cout << setw(z) << j << " \n"[j == (w - 1)];
  for (int i = 0; i < h; ++i) {
    cout << setw(z) << i;
    for (int j = 0; j < v[i].size(); ++j)
      cout << setw(z) << v[i][j] << " \n"[j == (v[i].size() - 1)];
  }
  cout << "\n";
}
template <typename... Args>
string fmt(const string &format, const Args &...args) {
  size_t size = snprintf(nullptr, 0, format.c_str(), args...) + 1;
  if (size <= 0) {
    throw runtime_error("Error during formatting.");
  }
  unique_ptr<char[]> buf(new char[size]);
  snprintf(buf.get(), size, format.c_str(), args...);
  return string(buf.get(), buf.get() + size - 1);
}
void writesln() { cout << endl; }
template <typename T, typename... Args>
void writesln(const T &head, const Args &...tail) {
  debug() << head << " ";
  writesln(tail...);
}
template <typename T>
void read(T &x) {
  cin >> x;
}
template <typename T, typename... Args>
void read(T &head, Args &...tail) {
  read(head), read(tail...);
}
void soln(int64_t __ntc, int64_t __tc) {
  int64_t n;
  cin >> n;
  vector<int64_t> pubsize(n), costs(n);
  map<int64_t, multiset<int64_t>> M;
  for (int64_t i = 0; i < n; ++i) {
    cin >> pubsize[i];
  }
  for (int64_t i = 0; i < n; ++i) {
    cin >> costs[i];
    M[pubsize[i]].insert(costs[i]);
  }
  int64_t s = 0;
  multiset<int64_t> C;
  int64_t sig = 0;
  int64_t tot = 0;
  while (true) {
    9;
    ;
    9;
    ;
    if (C.empty()) {
      assert(sig == 0);
      if (M.empty()) break;
      s = M.begin()->first;
      C = M.begin()->second;
      M.erase(M.begin());
      for (auto &i : C) sig += i;
    } else {
      tot += sig - *C.rbegin();
      sig -= *C.rbegin();
      C.erase(prev(C.end()));
      s += 1;
      auto it = M.find(s);
      if (it != M.end()) {
        for (auto &i : it->second) {
          C.insert(i);
          sig += i;
        }
        M.erase(s);
      }
    }
  }
  cout << tot << endl;
}
int64_t Solver() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  soln(1, 1);
  return 0;
}
signed main() { Solver(); }

```