#include int ri() { int n; scanf("%d", &n); return n; } template struct ModInt{ int x; ModInt () : x(0) {} ModInt (int64_t x) : x(x >= 0 ? x % mod : (mod - -x % mod) % mod) {} ModInt &operator += (const ModInt &p){ if ((x += p.x) >= mod) x -= mod; return *this; } ModInt &operator -= (const ModInt &p) { if ((x += mod - p.x) >= mod) x -= mod; return *this; } ModInt &operator *= (const ModInt &p) { x = (int64_t) x * p.x % mod; return *this; } ModInt &operator /= (const ModInt &p) { *this *= p.inverse(); return *this; } ModInt &operator ^= (int64_t p) { ModInt res = 1; for (; p; p >>= 1) { if (p & 1) res *= *this; *this *= *this; } return *this = res; } ModInt operator - () const { return ModInt(-x); } ModInt operator + (const ModInt &p) const { return ModInt(*this) += p; } ModInt operator - (const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator * (const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator / (const ModInt &p) const { return ModInt(*this) /= p; } ModInt operator ^ (int64_t p) const { return ModInt(*this) ^= p; } bool operator == (const ModInt &p) const { return x == p.x; } bool operator != (const ModInt &p) const { return x != p.x; } explicit operator int() const { return x; } ModInt &operator = (const int p) { x = p; return *this;} ModInt inverse() const { int a = x, b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); } return ModInt(u); } friend std::ostream & operator << (std::ostream &stream, const ModInt &p) { return stream << p.x; } friend std::istream & operator >> (std::istream &stream, ModInt &a) { int64_t x; stream >> x; a = ModInt(x); return stream; } }; typedef ModInt<998244353> mint; template struct MComb { using mint = ModInt; std::vector fact; std::vector inv; MComb (int n) { // O(n + log(mod)) fact = std::vector(n + 1, 1); for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * mint(i); inv.resize(n + 1); inv[n] = fact[n] ^ (mod - 2); for (int i = n; i--; ) inv[i] = inv[i + 1] * mint(i + 1); } mint ncr(int n, int r) { return fact[n] * inv[r] * inv[n - r]; } mint npr(int n, int r) { return fact[n] * inv[n - r]; } mint nhr(int n, int r) { assert(n + r - 1 < (int) fact.size()); return ncr(n + r - 1, r); } }; std::vector solve(std::vector > pts, int h, int w) { /* bool map[h + 1][w + 1]; memset(map, 0, sizeof(map)); for (auto i : pts) map[i.first][i.second] = true; std::vector dp[h + 1][w + 1]; dp[0][0] = { 1 }; for (int i = 0; i <= h; i++) for (int j = 0; j <= w; j++) { if (map[i][j]) dp[i][j].insert(dp[i][j].begin(), 0); if (i < h) { while (dp[i + 1][j].size() < dp[i][j].size()) dp[i + 1][j].push_back(0); for (int k = 0; k < (int) dp[i][j].size(); k++) dp[i + 1][j][k] += dp[i][j][k]; } if (j < w) { while (dp[i][j + 1].size() < dp[i][j].size()) dp[i][j + 1].push_back(0); for (int k = 0; k < (int) dp[i][j].size(); k++) dp[i][j + 1][k] += dp[i][j][k]; } } return dp[h][w]; */ //* pts.insert(pts.begin(), {0, 0}); pts.push_back({h, w}); int n = pts.size(); MComb<998244353> com(h + w); std::vector dp[n]; dp[0] = { 1 }; for (int i = 0; i < n; i++) { mint tmp = 0; for (int j = dp[i].size(); --j; ) { dp[i][j] -= tmp; tmp += dp[i][j]; } for (int j = i + 1; j < n; j++) { if (pts[j].second < pts[i].second) continue; mint times = com.ncr(pts[j].first - pts[i].first + pts[j].second - pts[i].second, pts[j].first - pts[i].first); while (dp[j].size() <= dp[i].size()) dp[j].push_back(0); for (int k = 0; k < (int) dp[i].size(); k++) dp[j][k + 1] += dp[i][k] * times; } } auto res = dp[n - 1]; res.erase(res.begin()); return res;//*/ } int main() { int n = ri(); int m = ri(); int l = ri(); int k = ri(); std::vector > check_pts(m); for (auto &i : check_pts) i.first = ri(), i.second = ri(); check_pts.insert(check_pts.begin(), std::pair(0, 0)); check_pts.push_back({n, n}); std::vector > tigers(l); for (auto &i : tigers) i.first = ri(), i.second = ri(); std::sort(tigers.begin(), tigers.end()); { std::vector > tmp; for (int i = 0; i < l; i++) { int x = tigers[i].first; int y = tigers[i].second; auto itr = std::lower_bound(check_pts.begin(), check_pts.end(), std::pair{x, y}); if (y < std::prev(itr)->second || y > itr->second) continue; tmp.push_back(tigers[i]); } tigers = tmp; l = tigers.size(); } int head = 0; std::vector dp{1}; for (int i = 1; i < (int) check_pts.size(); i++) { int old_head = head; while (head < l && tigers[head].first <= check_pts[i].first) head++; std::vector > pts; for (int j = old_head; j < head; j++) pts.push_back({tigers[j].first - check_pts[i - 1].first, tigers[j].second - check_pts[i - 1].second}); auto tmp = solve(pts, check_pts[i].first - check_pts[i - 1].first, check_pts[i].second - check_pts[i - 1].second); /* for (auto i: tmp) std::cerr << i << " "; std::cerr << std::endl;*/ std::vector next(dp.size() + tmp.size() - 1); for (int i = 0; i < (int) dp.size(); i++) for (int j = 0; j < (int) tmp.size(); j++) next[i + j] += dp[i] * tmp[j]; dp = next; } mint res = 0; for (int i = 0; i < (int) dp.size() && i <= k; i++) res += dp[i]; std::cout << res << std::endl; return 0; }