#216690. [MCO 2026] 制造连招

龙 Evirir 正在玩一款电子游戏，它想通过连续释放技能来使总伤害最大化。

Evirir 可以使用 个不同的技能，编号为 。对于每个技能 ，它的颜色为 ，伤害为 。共有 条技能连接，每条连接是一个技能对 ，其中 。

一个连招是一个长度为 的技能序列 ，满足对于所有 ， 都是这 条技能连接之一。题目保证输入中的技能连接不会形成环。也就是说，不可能构建一个包含同一技能两次的连招。

该连招的总威力按如下方式计算。设有一个倍率 ，初始时 。对于 ，依次进行：

• 如果 ，则不做任何事。
• 否则：
  • 如果技能 和 的颜色相同，则将 乘以 。
  • 如果技能 和 的颜色不同，则将 设为 。
• 然后，技能 的威力为 。

连招的总威力就是所有已释放技能威力之和。

例如，假设某个连招按顺序包含如下技能：、、、、、、，其中 表示一个伤害为 、颜色为 的技能。计算过程如下：

因此，这个连招的总威力为 。

显然，Evirir 想要施放一个总威力最大的连招。为此，它安装了一个外挂，可以将任意技能的颜色改成一个固定颜色 。Evirir 最多只能使用这个外挂 次（也就是说，最多只能修改 个技能的颜色）。

求 Evirir 能达到的最大总威力是多少。如果最大总威力严格大于 ，输出 。

第一行包含四个用空格分隔的整数 、、 和 。

接下来有 行，其中第 行包含两个用空格分隔的整数 和 。

接下来有 行，其中第 行包含两个用空格分隔的整数 和 。

输出一个整数，表示可能的最大总威力。如果它严格大于 ，则输出 。如果它恰好等于 ，则应输出 。

样例输入 1

6 7 2 1
3 1
2 3
4 1
5 2
1 5
2 0
0 1
3 4
2 3
0 3
3 5
1 2
0 5

样例输出 1

65

样例输入 2

5 4 0 5
2 0
3 1
2 0
3 0
13 0
0 1
1 2
2 3
3 4

样例输出 2

65

样例输入 3

4 3 4 0
100000000 0
100000000 1
100000000 2
100000000 3
0 1
1 2
2 3

样例输出 3

-1

提示

这个样例符合子任务 4 和 7。

下面给出一个可视化图示。从技能 指向技能 的箭头表示存在一条技能连接 ，也就是说 Evirir 可以在技能 之后立刻使用技能 。左上角的大圆圈说明了每个数字的含义。

:::align{center} :::

Evirir 最多可以将 个技能的颜色改为颜色 。它可以把技能 和 的颜色改为 ，然后施放技能序列 。总威力为 。

一个不是连招的例子是技能序列 ，因为 不是这 条技能连接之一。

这个样例符合子任务 2、3、4、5、6、和 7。

共有 个技能和 条技能连接。，因此 Evirir 不能修改任何技能的颜色。 最优连招是施放技能 。总威力为 。

这个样例符合子任务 1、3、4、5、6、和 7。

由于 ，Evirir 可以将技能 、 和 的颜色改为颜色 。最优连招是施放技能 。总威力为 。由于最大可能总威力严格大于 ，因此输出 。

评分

对于所有测试用例，输入满足以下限制：

• 对所有 ，有
• 对所有 ，有
• 。注意， 可能等于 ，即一个未被使用的颜色。
• 对所有 ，有 且
• 对所有 ，数对 两两相异。
• 保证技能连接不会形成环。也就是说，不可能构建一个包含同一技能两次的连招。