#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

mt19937 mrand(random_device{} ());

int rnd(int x) {
  return mrand() % x;
}

const int maxn = (int) 1e5 + 5;
int n;
int d[maxn], c[maxn];
vector<int> g[maxn];
long long s[maxn];
map<long long, long long> *mps[maxn];

struct CoverTreePaths {
  long long minimumCost(int _n, vector<int> pp, vector<int> dd, vector<int> cc, vector<int> params) {
    n = _n;
    for (int i = 0; i < n; i++) {
      g[i].clear();
    }
    {
      int t = sz(dd);
      for (int i = 0; i < t - 1; i++) {
        g[pp[i]].push_back(i + 1);
      }
      int x = pp[t - 2];
      for (int i = t - 1; i < n - 1; i++) {
        x = ((long long) params[0] * x + params[1]) % (i + 1);
        g[x].push_back(i + 1);
      }
      for (int i = 0; i < t; i++) {
        d[i] = dd[i];
      }
      x = dd[t - 1];
      for (int i = t; i < n; i++) {
        x = 1 + ((long long) params[2] * x + params[3]) % params[4];
        d[i] = x;
      }
      for (int i = 0; i < t; i++) {
        c[i] = cc[i];
      }
      x = cc[t - 1];
      for (int i = t; i < n; i++) {
        x = 1 + ((long long) params[5] * x + params[6]) % params[7];
        c[i] = x;
      }
    }
    for (int v = n - 1; v >= 0; v--) {
      mps[v] = new map<long long, long long>();
      auto &mpv = mps[v];
      s[v] = 0;
      for (int i = 0; i < sz(g[v]); i++) {
        int u = g[v][i];
        auto mpu = mps[u];
        if (sz(*mpv) < sz(*mpu)) {
          swap(mpv, mpu);
        }
        for (auto it = mpu->begin(); it != mpu->end(); it++) {
          (*mpv)[it->first] += it->second;
        }
        s[v] += s[u];
      }
      while (true) {
        if (!mpv->empty()) {
          auto it = mpv->end();
          it--;
          if (it->first >= -d[v]) {
            s[v] -= it->second;
            mpv->erase(it);
            continue;
          }
          if (s[v] >= c[v]) {
            if (s[v] - it->second < c[v]) {
              it->second -= s[v] - c[v];
              s[v] = c[v];
              break;
            }
            s[v] -= it->second;
            mpv->erase(it);
            continue;
          }
        }
        (*mpv)[-d[v]] = c[v] - s[v];
        s[v] = c[v];
        break;
      }
    }
    auto mp = *mps[0];
    long long val = 0;
    long long d = 0;
    for (auto it = mp.begin(); it != mp.end(); it++) {
      d += it->second;
      auto nit = it;
      nit++;
      long long x;
      if (nit == mp.end()) {
        x = -it->first;
      } else {
        x = nit->first - it->first;
      }
      val += x * d;
    }
    return val;
  }
};