問題文

N 個の石油タンクがあり、i (1 \leq i \leq N) 番目の石油タンクには C_i リットルまでの石油が入ります。はじめ、すべての石油タンクは空です。

石油を買いに、客が1人ずつやってきます。各客は、買いたい石油の量 D リットルと、待てる時間 T 分を提示します。D および T はランダムに決められます。

T 分以内に 1 つ以上の石油タンクを組み合せて、ちょうど D リットルの石油を用意すると、客は料金を D^2 だけ払ってくれます。石油を購入した客は帰り、すぐに新しい客が来ます。

石油を用意できずに T 分経ってしまうと、客は帰ってしまいます。その場合も、すぐに新しい客が来ます。

あなたは毎分、以下のいずれかの行動を実行しなければいけません。

• fill i: i 番目の石油タンクに石油を満たします。すでに石油が満たされている場合は何も起こりません。
• move i j: i 番目の石油タンクの石油を、j 番目の石油タンクに移します。i 番目の石油タンクに入っている石油が j 番目のタンクの空きよりも多い場合、 j 番目のタンクがいっぱいになるまで石油を入れ、入り切らなかった石油は i 番目のタンクに残ります。そうでなかった場合、i 番目の石油タンクに入っている石油を j 番目のタンクに全て移します。
• change i: i 番目の石油タンクを、新しい空の石油タンクに交換します。もし石油が i 番目のタンクに残っていた場合、それは捨てられます。新しいタンクの容量 C_i はランダムに決められます。
• pass: 今いる客に帰ってもらいます。すぐに新しい客が来ます。
• sell n x_1 x_2 x_3 ... x_n: x_{1} 番目、x_{2} 番目、x_{3} 番目、… x_{n} 番目の n 個の石油タンクを売り渡します。このとき、n 個の石油タンクに含まれる石油の量の合計量は、ちょうど D でなければいけません。また、空のタンクを売り渡すことはできません。売り渡したタンクは、新しい空のタンクに交換されます。新しいタンクの容量 C_i はランダムに決められます。

これらの行動を 1000 回繰り返すことで、得られる料金の合計を最大化してください。

制約

• N = 8
• 1 \leq C_i \leq 10 (1 \leq i \leq N)
• 1 \leq D \leq 50
• 1 \leq T \leq 10
• C_i (1 \leq i \leq N), D, T の値は整数であり、一様乱数によってランダムに決定されます。

採点について

各テストケースについて、得られた料金の合計が、そのテストケースの得点になります。

テストケースは全部で 50 個あります。各テストケースの得点の合計値が、この問題の得点になります。

フォーマットに違反した出力を行った場合や、1000回の入出力を行わずにプログラムが終了した場合の結果は定義されていません (WA とは限りません)。

入出力例

3 2
6 2 3 2 9 10 7 7
0 0 0 0 0 0 0 0

fill 1

3 1
6 2 3 2 9 10 7 7
6 0 0 0 0 0 0 0

move 1 4

6 8
6 2 3 2 9 10 7 7
4 0 0 2 0 0 0 0

sell 2 1 4

5 5
1 2 3 5 9 10 7 7
0 0 0 0 0 0 0 0

change 2

5 4
1 1 3 5 9 10 7 7
0 0 0 0 0 0 0 0

pass

8 2
1 1 3 5 9 10 7 7
0 0 0 0 0 0 0 0

出力の flush について

この問題では、各入力ごとに、それに対する出力を flush する必要があります。主要な言語について、出力を flush する例を紹介します。どの例でも pass と出力して改行して flush しています。

C++

std::cout << "pass" << std::endl;

Java

System.out.println("pass");

Python 3.4

print("pass", flush=True)

テスター

テスターを次のリンクから提供しています。

テスター