/**
 * @brief ユーザ定義リテラル
 * @author えびちゃん
 */

#ifndef H_int_literals
#define H_int_literals

#include <cstddef>
#include <cstdint>

constexpr intmax_t  operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t    operator ""_zu(unsigned long long n) { return n; }
constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }

#endif  /* !defined(H_int_literals) */

/**
 * @brief 多次元 vector の作成
 * @author えびちゃん
 */

#ifndef H_make_vector
#define H_make_vector

#include <cstddef>
#include <type_traits>
#include <vector>

namespace detail {
  template <typename Tp, size_t N>
  std::vector<Tp> make_vector(
      std::vector<size_t>& sizes,
      typename std::enable_if<(N == 1), Tp const&>::type x
  ) {
    return std::vector<Tp>(sizes[0], x);
  }
  template <typename Tp, size_t N>
  auto make_vector(
      std::vector<size_t>& sizes,
      typename std::enable_if<(N > 1), Tp const&>::type x
  ) {
    size_t size = sizes[N-1];
    sizes.pop_back();
    return std::vector<decltype(make_vector<Tp, N-1>(sizes, x))>(
        size, make_vector<Tp, N-1>(sizes, x)
    );
  }
}  // detail::

template <typename Tp, size_t N>
auto make_vector(size_t const(&sizes)[N], Tp const& x = Tp()) {
  std::vector<size_t> s(N);
  for (size_t i = 0; i < N; ++i) s[i] = sizes[N-i-1];
  return detail::make_vector<Tp, N>(s, x);
}

#endif  /* !defined(H_make_vector) */

/**
 * @brief ラムダ式の再帰
 * @author えびちゃん
 */

#ifndef H_make_fix_point
#define H_make_fix_point

#include <utility>

template <typename Fn>
class fix_point: Fn {
public:
  explicit constexpr fix_point(Fn&& f) noexcept: Fn(std::forward<Fn>(f)) {}

  template <typename... Args>
  constexpr decltype(auto) operator ()(Args&&... args) const {
    return Fn::operator ()(*this, std::forward<Args>(args)...);
  }
};

template <typename Fn>
static inline constexpr decltype(auto) make_fix_point(Fn&& f) noexcept {
  return fix_point<Fn>{std::forward<Fn>(f)};
}

#endif  /* !defined(H_make_fix_point) */

#include <cstdio>
#include <cstdint>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>

template <typename Fn>
auto monotone_minima(Fn&& f, size_t h, size_t w) {
  using value_type = decltype(f(h, w));
  std::vector<size_t> res(h);

  make_fix_point([&](auto dfs, size_t hl, size_t hu, size_t wl, size_t wu) -> void {
      if (hl >= hu) return;
      size_t hm = (hl+hu) >> 1;
      value_type min = f(hm, wl);
      res[hm] = wl;
      for (size_t j = wl+1; j < wu; ++j) {
        value_type cur = f(hm, j);
        if (cur < min) {
          min = std::move(cur);
          res[hm] = j;
        }
      }
      if (hl == hm) return;
      dfs(hl, hm, wl, res[hm]+1);
      dfs(hm+1, hu, res[hm], wu);
  })(0, h, 0, w);
  return res;
}

int main() {
  size_t n, m, d;
  intmax_t x;
  scanf("%zu %zu %zu %jd", &n, &m, &d, &x);

  std::vector<intmax_t> p(n);
  for (auto& pi: p) scanf("%jd", &pi);

  std::vector<intmax_t> q(m);
  for (auto& qi: q) {
    intmax_t a, b;
    scanf("%jd %jd", &a, &b);
    qi = a - std::abs(b);
  }

  intmax_t const inf = 1e18;
  intmax_t res = inf;
  auto dp = make_vector({n}, inf);
  dp[0] = 0;
  for (size_t dd = 0; dd < d; ++dd) {
    std::vector<intmax_t> w(n+1, 0);
    w[0] = m;
    for (auto const& qi: q) {
      size_t i = std::upper_bound(p.begin(), p.end(), qi) - p.begin();
      --w[i];
    }
    for (size_t i = 1; i <= n; ++i) w[i] += w[i-1];

    auto tmp = make_vector({n}, inf);

    auto f = [&](size_t i, size_t j) -> intmax_t {
      if (!(j < i)) return inf;
      return dp[j] + w[j] * (p[i]-p[j]);
    };
    auto prev = monotone_minima(f, n, n);

    for (size_t i = 0; i < n; ++i)
      tmp[i] = f(i, prev[i]);

    dp = std::move(tmp);
    res = std::min(res, dp[n-1]);
    for (auto& qi: q) qi += x;
  }

  printf("%jd\n", res);
}



Measured memory_bytes: 3036