/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
あなたは、1 から N までの番号が振られた N 本の棒を使って輪投げをします。
輪投げは ラウンド 1、ラウンド 2、ラウンド 3 の 3 つのラウンドに分かれていて、各ラウンドではあなたは必ず M 本の相異なる棒に輪を命中させます。輪は必ずすべて投げなければならず、各ラウンドで命中させた輪はそのラウンドが終わっても棒に残されることに注意してください。
ラウンド i で輪を棒 j に命中させると、あなたは (A_{j} \times (B_{j})^{i} \mod R_{i}) 点を得ます。
しかし、同じ棒にたくさん輪がかかっているのは面白くありません。各棒にかかっている輪の個数の一様性をできるだけ保たせるために、次のルールが追加されます: すべてのラウンドが終了した後、1 個以上の輪がかかっている各棒 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, 2, 3 のそれぞれにおいて、輪を棒 1 に命中させて得られる得点は 9, 27, 81 点です。
- ラウンド 1, 2, 3 のそれぞれにおいて、輪を棒 2 に命中させて得られる得点は 6, 18, 54 点です。
- すべてのラウンドの終了後、棒 1 に輪が 1, 2, 3 本かかっているときに減点される点数は、それぞれ 9, 27, 81 点です。
- すべてのラウンドの終了後、棒 2 に輪が 1, 2, 3 本かかっているときに減点される点数は、それぞれ 6, 18, 54 点です。
最適な戦略は、ラウンド 1 では輪を棒 2 に、ラウンド 2, 3 では輪を棒 1 に命中させることです。
入力例 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
Score : 6 points
Warning
Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
You are playing a quoits game with N pins numbered from 1 to N.
The game is divided into three rounds, round 1, round 2, and round 3. In each round, you will hit exactly M distinct pins by throwing hoops. You have to throw all the hoops, and the hoops you have made encircle the pins (i.e. hit) in each round will remain in that place until the game ends.
If you hit the pin j in the round i, you will gain (A_{j} \times (B_{j})^{i} \mod R_{i}) points.
However, having the same pins encircled by many hoops is not exciting. In order to encourage the uniformity of the number of hits for each pin, you get another rule: after the game is over, if the pin j is being encircled by a positive number of hoops, in particular, by i hoops, then you will lose A_{j} \times (B_{j}) ^{i} points. Thus, your total points might be negative.
You want to maximize the total points you can get by wisely deciding which set of pins you will hit in each round.
Constraints
- All the values in the input are integers.
- 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}
Input
Input is given from Standard Input in the following format:
N M
A_{1} A_{2} \ldots A_{N}
B_{1} B_{2} \ldots B_{N}
R_{1} R_{2} R_{3}
Output
Print a single integer - the maximum possible total points you can gain.
Sample Input 1
2 1 3 2 3 3 100000 100000 100000
Sample Output 1
81
In each round, if you hit the pin 1, you will gain 9, 27, 81 points, respectively.
In each round, if you hit the pin 2, you will gain 6, 18, 54 points, respectively.
After the all rounds end, if the pin 1 is encircled by 1, 2, 3 hoops, then you will lose 9, 27, 81 points, respectively.
After the all rounds end, if the pin 2 is encircled by 1, 2, 3 hoops, then you will lose 6, 18, 54 points, respectively.
The optimal way in this example is to hit the pin 2 in the round 1 and hit the pin 1 in the round 2, and 3.
Sample Input 2
4 2 2 4 3 3 4 2 3 3 100000 100000 100000
Sample Output 2
210
Sample Input 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
Sample Output 3
-1417