← 返回题目列表

AtCoder · past202005_o

O. 引号

中文机器翻译题面 查看原题

分数: 6 点

警告

2020 年 6 月 6 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

您正在玩圆环游戏 N 引脚编号为 1 to N.

比赛分为三轮,回合 1,圆形 2,和圆形 3。在每一轮中,你都会准确击中 M 通过投掷篮圈来区分不同的别针。你必须投掷所有的圆环,并且你在每轮中围绕球瓶(即击中)的圆环将保留在该位置,直到游戏结束。

如果你击中了别针 j 全面 i,您将获得 (A_{j} \times (B_{j})^{i} \mod R_{i}) 点。

然而,相同的销钉被许多箍圈住并不令人兴奋。为了鼓励每个瓶的击中次数的一致性,你得到另一个规则:游戏结束后,如果瓶 j 被正数的圆圈包围,特别是 i 篮球,那你就输了 A_{j} \times (B_{j}) ^{i} 点。因此,您的总分可能为负数。

您希望通过明智地决定每轮击中哪组瓶来最大化您可以获得的总分。

约束

  • 输入中的所有值都是整数。
  • 1 \leq M \leq N \leq 500
  • 2 \leq A_{i}, B_{i} \leq 1000
  • 2 \leq R_{1}, R_{2}, R_{3} \leq 10^{5}

输入

输入由标准输入按以下格式给出:

N M
A_{1} A_{2} \ldots A_{N}
B_{1} B_{2} \ldots B_{N}
R_{1} R_{2} R_{3}

输出

打印一个整数 - 您可以获得的最大可能总分。


示例输入 1

2 1
3 2
3 3
100000 100000 100000

示例输出 1

81

在每一轮中,如果你击中了瓶针 1,您将获得 9, 27, 81 点。

在每一轮中,如果你击中了瓶针 2,您将获得 6, 18, 54 点。

所有回合结束后,如果 1 被包围 1, 2, 3 篮球,那你就输了 9, 27, 81 点。

所有回合结束后,如果 2 被包围 1, 2, 3 篮球,那你就输了 6, 18, 54 点。

本例中的最佳方式是击中瓶针 2 全面 1 并击中别针 1 全面 2, 和 3.


示例输入 2

4 2
2 4 3 3
4 2 3 3
100000 100000 100000

示例输出 2

210

示例输入 3

20 19
3 2 3 4 3 3 2 3 2 2 3 3 4 3 2 4 4 3 3 4
2 3 4 2 4 3 3 2 4 2 4 3 3 2 3 4 4 4 2 2
3 4 5

示例输出 3

-1417