题目背景

小 C 和小 D 是好朋友。他们正在尝试一种全新的牌类游戏——onu！

题目描述

为了增加一点趣味性，小 C 和小 D 每人买了 $v$ 颗糖用来当作筹码。

onu 的规则是这样的：

游戏共 $m$ 轮，由两人进行，一位先手，一位后手。在这里，我们默认先手的玩家是小 C，而后手的玩家是小 D。

在最开始时，小 C 会得到 $m$ 张牌，每张牌有其对应的花色、点数。而小 D 会得到 $n$ 张牌。

每一轮开始时，小 C 会打出一张牌，放在桌面上展示给小 D 看。

在此之后，小 D 需要跟牌，即打出他手上的一张牌，且该张牌必须满足其花色与小 C 打出的牌相同。若小 D 没有满足条件的牌或者是他选择弃权（也就是说，可以选择当前回合是否打出牌），弃掉小 C 打出的牌后跳过该轮，视为小 D 败。

在小 D 打出满足要求的牌后，进行一次拼点，也即比较小 C 和小 D 打出的牌的点数：如果小 D 出的牌的点数大于等于小 C 的牌的点数，则小 D 胜，否则小 D 败。容易知道，这样不会出现平局的情况。

最后，胜的一方会从败的一方拿走 $c$ 颗糖，且双方均需弃掉打出的牌，并会再从商店买等于自己打出的牌的点数颗糖。例如小 C 和小 D 打的点数分别是 $3$ 和 $5$，那么小 C 会去购买 $3$ 颗糖，小 D 购买 $5$ 颗。

为了不破坏两人间的友好关系，不出现一方被另一方完全赢光的情况，他们在最开始买糖时，已经约定好了 $v \ge c \times m$。

现在，小 D 通过一些神秘手段，知道了小 C 在这 $m$ 轮中打出的所有牌，他希望在 $m$ 轮游戏进行之后，让自己的糖数尽量多。你可以帮他找到最优的方案吗？

输入格式

第一行四个正整数表示 $n, m, c, v$，含义如题目描述所示。

接下来 $n$ 行中，第 $i$ 行每行两个正整数 $a _i, b _i$，表示了小 D 一开始拥有的第 $i$ 张牌的花色、点数。

接下来 $m$ 行中，第 $i$ 行每行两个正整数 $a _i, b _i$，表示小 C 第 $i$ 轮会打出的牌的花色、点数。

注意可能会有花色点数均相同的牌。

输出格式

输出共 $m + 1$ 行。

第一行输出一个正整数，表示在最优方案中，小 D 最多能剩余的糖数。

接下来 $m$ 行中，第 $i$ 行输出一行一个正整数，表示小 D 在第 $i$ 轮打出的牌的编号。如果小 D 跳过了该轮，输出 -1。

本题采用 Special Judge，如果有多种最优方案，输出任意一个即可。

3 3 1 4
3 5
1 2
2 6
1 6
3 5
1 4

10
2
1
-1

1 2 1 5
1 5
1 8
1 4

10
-1
1

提示

「样例 1 解释」

以 $(a, b)$ 来表示一张花色为 $a$，点数为 $b$ 的牌。

一开始，小 D 有 $4$ 颗糖。小 C 会依次打出 $(1, 6), (3, 5), (1, 4)$ 三张牌。

一种最优的方案是：

第一轮，小 C 打出第一张牌 $(1, 6)$，小 D 打出第二张牌 $(1, 2)$，小 D 负，被拿走 $1$ 颗糖，购买 $2$ 颗糖。此时其有 $5$ 颗糖。

第二轮，小 C 打出 $(3, 5)$，小 D 打出 $(3, 5)$，由于点数大于等于小 C 的牌，所以小 D 胜，拿到 $1$ 颗糖，购买 $5$ 颗糖。此时其有 $11$ 颗糖。

第三轮，小 C 打出 $(1, 4)$。由于小 D 在第一轮已经打出过第二张牌 $(1, 2)$ 了，所以没有牌能打，输出 $-1$ 并判小 D 负，被拿走 $1$ 颗糖，此时其有 $10$ 颗糖。

「样例 2 解释」

最开始有 $5$ 颗糖。

第一轮时小 C 打出 $(1, 8)$，小 D 选择弃权，败，于是剩下了 $5 - 1 = 4$ 颗糖；

第二轮时小 C 打出 $(1, 4)$，小 D 打出 $(1, 5)$，胜，得到 $5 + 1$ 颗糖，故最终小 D 有 $10$ 颗糖。

---

「Special Judge 说明」

请认真阅读输出格式。

每个测试点仅有 $0$ 分和满分的区别。如果你的输出出现了以下情况，将会被判为 $0$ 分：

• 输出格式不符，如没有正确换行，输出了一些奇奇怪怪的字符等。
• 输出的最优糖果数与标准答案不同。
• 打牌的方案不合法，即不能打出已经弃掉的牌，也不能打出花色与小 C 打出的牌不相同的牌。
• 按照你所输出的方案打完牌后，小 D 的剩余糖果数与你第一行所输出的数字不同。

---

「数据范围」

本题采用捆绑测试。

• Subtask 1(10 points)：$n, m \le 5$；
• Subtask 2(30 points)：$n, m \le 1000$；
• Subtask 3(20 points)：$c = 0$；
• Subtask 4(20 points)：$a _i = 1$；
• Subtask 5(20 points)：无特殊限制。

所有数据保证 $1 \le n, m, a _i, b _i\le 10 ^5$，$0 \le c \le 10 ^5$，$c \times m \le v \le 10 ^{12}$。