有 $n$ 只怪物排成一排，每只怪物有两个已知属性：$h_i$ 表示怪物的生命值，$r_i$ 表示击败该怪物后获得的奖励（以金币计）。骑士必须击败所有的怪物。

为了击败怪物，骑士拥有 $m$ 种类型的剑，每种剑的属性已知：$s_j$ 表示剑的强度，$c_j$ 表示剑的价格（以金币计）。购买价格为 $c_j$ 的剑时，骑士必须拥有至少 $c_j$ 枚金币。购买剑后，骑士的金币数量会减少 $c_j$。初始时，骑士拥有 $x$ 枚金币。

购买一把剑后，它最多可以在与怪物的战斗中使用 $k$ 次。任何类型的剑都可以购买任意多次。强度为 $s_j$ 的剑可以击败生命值为 $h_i$ 的怪物，前提是 $s_j \ge h_i$。在任何时刻，骑士只能持有一把剑，这意味着购买新剑后，旧剑将无法继续使用（但未来可以再次购买）。

怪物必须按固定顺序击败：从第一只到最后一只。请确定骑士是否能够完成任务。

输入格式

第一行包含四个整数 $n, m, k$ 和 $x$ ($1 \le n, m \le 500\,000, 1 \le k \le n, 1 \le x \le 10^9$)，分别表示怪物数量、剑的种类数、剑最多可使用的次数以及骑士初始拥有的金币数量。

接下来的 $n$ 行描述怪物。第 $i$ 行包含两个整数 $h_i$ 和 $r_i$ ($1 \le h_i, r_i \le 10^9$)，分别表示第 $i$ 只怪物的生命值和击败它获得的奖励。

接下来的 $m$ 行描述剑的属性。第 $j$ 行包含两个整数 $s_j$ 和 $c_j$ ($1 \le s_j, c_j \le 10^9$)，分别表示第 $j$ 种剑的强度和价格。

输出格式

如果骑士能够击败所有怪物，输出 “Yes”（不含引号），否则输出 “No”（不含引号）。

样例

输入格式 1

3 3 2 5
1 1
5 5
9 5
9 10
1 1
5 1

输出格式 1

Yes

说明

在第一个样例中，骑士可以先购买第三种剑，用它击败第一只和第二只怪物。之后，他将拥有 $5 - 1 + 1 + 5 = 10$ 枚金币。这使他能够购买第一种剑并击败最后一只怪物。

输入格式 2

5 5 5 6
3 6
2 4
1 1
4 4
8 4
2 7
7 7
3 4
5 9
6 4

输出格式 2

No

说明

在第二个样例中，骑士无法击败所有怪物，因为没有任何一种剑可以击败第五只怪物。

说明

本题共有 9 个测试组。仅当通过某组的所有测试点以及之前某些组的所有测试点时，才能获得该组的分数。注意，某些组不需要通过样例测试。离线测试意味着该组的测试结果仅在比赛结束后公布。每组的最终得分为所有提交记录中该组测试所获得的最高分。

子任务