/**
 * @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) const { return m * v + b; }
};
struct Line {
  int64_t w, t;
  int64_t operator()(int64_t dist) const { 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::set<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::set<Node> cur;
  // deletes [l, r]
  auto del = [&](int64_t l, int64_t r) {
    auto it = nxt.lower_bound(Node{0, 0, l});
    while (it != nxt.end() && it->r <= r) {
      nxt.erase(it++);
    }
  };
  nxt.insert(Node{1, 0, (int64_t)4e18});
  for (int i = m - 2; i >= 0; --i) {
    Node pre;
    int64_t mx = -1;
    for (Line &l : b[i]) {
      if (l(s[i + 1] - s[i]) <= mx) {
        continue;
      }
      // apply pre
      int64_t r = std::min(l.t, mx);
      if (r != -1) {
        del(pre.r + 1, r);
        pre.r = r;
        cur.insert(pre);
      }
      if (l.t > mx) {
        auto it = nxt.lower_bound(Node{0, 0, l.t});
        auto node = *it;
        node.r = l.t;
        cur.insert(node);
      }
      mx = l(s[i + 1] - s[i]);
      auto it = nxt.lower_bound(Node{0, 0, mx});
      pre = {0, (*it)(mx), l.t};
    }
    del(pre.r + 1, mx);
    pre.r = mx;
    cur.insert(pre);
    nxt.merge(cur);
    dbg((int)nxt.size());
  }
}

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