AT_past202005_o 輪投げ

[problemUrl]: https://atcoder.jp/contests/past202005-open/tasks/past202005_o あなたは、$ 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} $ 点減算されます。このため、最終得点は負となる可能性もあります。 あなたは、各ラウンドにどの棒を命中させるか適切に決めることで最終得点を最大化しようとしています。

入力は以下の形式で標準入力から与えられる. > $ N $ $ M $ $ A_{1} $ $ A_{2} $ $ \ldots $ $ A_{N} $ $ B_{1} $ $ B_{2} $ $ \ldots $ $ B_{N} $ $ R_{1} $ $ R_{2} $ $ R_{3} $

あなたの最終得点の最大値を整数として出力せよ。

### 注意 この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - 入力は全て整数 - $ 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} $ ### Sample Explanation 1 \- ラウンド $ 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 $ に命中させることです。