/**
 * @file qoj7122-1.cpp
 * @author n685
 * @brief
 * @date 2023-12-28
 *
 *
 */
#include "overtaking.h"
#include <bits/stdc++.h>

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif

struct Node {
  int64_t m = 1, b = 0;
  int64_t r = -1;
  bool operator<(const Node &b) const { return r < b.r; }
  int64_t operator()(int64_t v) { return m * v + b; }
};
struct Line {
  int64_t w, t;
  int64_t operator()(int64_t dist) { return w * dist + t; }
  bool operator<(const Line &b) const {
    return std::pair{t, w} < std::pair{b.t, b.w};
  }
};

int64_t ll;
int m;
std::vector<int64_t> s;
int64_t x;
std::vector<std::vector<Line>> b;
std::vector<Node> nxt;
int n;

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X,
          int M, std::vector<int> S) {
  ll = L;
  m = M;
  s.resize(m);
  x = X;
  std::transform(S.begin(), S.end(), s.begin(),
                 [&](auto a) { return (int64_t)a; });
  b.resize(m);
  for (int i = 0; i < N; ++i) {
    if (W[i] <= X) {
      continue;
    }
    b[0].push_back(Line{W[i] - x, T[i]});
  }
  std::sort(b[0].begin(), b[0].end());
  n = (int)b[0].size();
  for (int i = 1; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
      if (j == 0) {
        b[i].push_back(Line{b[i - 1][j].w, b[i - 1][j](s[i] - s[i - 1])});
      } else {
        b[i].push_back(
            Line{b[i - 1][j].w,
                 std::max(b[i].back().t, b[i - 1][j](s[i] - s[i - 1]))});
      }
    }
    std::sort(b[i].begin(), b[i].end());
  }

  std::vector<Node> cur;
  nxt.push_back(Node{1, 0, (int64_t)4e18});
  for (int i = m - 2; i >= 0; --i) {
    Node pre;
    int64_t mx = -1;
    int ind = 0;
    auto det = [&]() {
      if (cur.empty()) {
        return mx;
      } else {
        return std::max(mx, cur.back().r + 1);
      }
    };
    for (Line &l : b[i]) {
      if (l(s[i + 1] - s[i]) <= mx) {
        continue;
      }
      int64_t r = std::min(l.t, mx);
      if (mx != -1) {
        pre.r = r;
        cur.push_back(pre);
      }
      if (l.t >= mx) {
        ind = std::lower_bound(nxt.begin(), nxt.end(), Node{0, 0, det()}) -
              nxt.begin();
        for (; ind < (int)nxt.size(); ++ind) {
          if (nxt[ind].r >= mx) {
            cur.push_back(nxt[ind]);
            if (cur.back().r > l.t) {
              cur.back().r = l.t;
              break;
            }
          }
        }
      }
      mx = l(s[i + 1] - s[i]);
      ind = std::lower_bound(nxt.begin(), nxt.end(), Node{0, 0, det()}) -
            nxt.begin();
      for (; ind < (int)nxt.size(); ++ind) {
        if (nxt[ind].r >= mx) {
          pre = Node{0, nxt[ind](mx), -1};
          break;
        }
      }
    }
    pre.r = mx;
    cur.push_back(pre);
    ind = std::lower_bound(nxt.begin(), nxt.end(), Node{0, 0, det()}) -
          nxt.begin();
    for (; ind < (int)nxt.size(); ++ind) {
      cur.push_back(nxt[ind]);
    }
    nxt = cur;
    cur.clear();
  }
}

long long arrival_time(long long Y) {
  auto it = *std::lower_bound(nxt.begin(), nxt.end(), Node{0, 0, Y});
  return it(Y) + x * ll;
}