Problem
TV チャンネルの 1 つで、次の宝くじが毎週開催されます。週の間、参加者は賭けをします。各賭けは、基数 K 数システムで M 桁の数字を指定することで構成されます (つまり、各参加者は M 桁の数字を指定し、それぞれが 0 から K & マイナス 1 までの範囲にあります)。数字には先行ゼロを使用できます。
ある時点で、現在の抽選への賭けが終了し、その後、プレゼンターがテレビで当選番号を発表します (これは、K-ary 番号システムの M 桁の番号でもあります)。その後、番号の最初の桁がホストによって指定された番号の最初の桁と一致したテレビ視聴者は、A
1 ルーブルの額の賞金を受け取ります。 — の最初の 2 桁が一致した人A
2 ルーブルを受け取ります (同時に、プレイヤーが 2 桁目を一致させ、1 桁目を一致させなかった場合、プレーヤーは何も受け取りません)。同様に、最初の 3 桁を当てた人は A
3 ルーブルを受け取ります。等々。整数を完全に推測した人は、Am ルーブルを受け取ります。さらに、プレーヤーが最初の t 桁を推測した場合、プレーヤーは A
t ルーブルを受け取りますが、t−1、t−2 などを推測しても賞金は受け取りません。数字。プレーヤーが最初の数字を当てられなかった場合、何も得られません。
視聴者が行った既知の賭けが与えられた場合に、主催会社が賞金として最低額を支払うために、テレビの司会者が名前を付ける必要がある番号を見つけるプログラムを作成します。便宜上、プレイヤーによるベットはすでに降順でソートされていません。
入力
最初の行には、数字 N (賭けをした TV 視聴者の数、1N100000)、M (数字の長さ 1M10)、K (数字システムの基数 2 ≤ K ≤ 10) が含まれています。次の行には、M 個の整数 A
1、A
2、...、A
M が含まれており、最初の 2 つだけの場合のペイオフを指定します。 ... 、すべての数字 (1 ≤ A
1 ≤ A
2 ≤ ... ≤ A
M ≤ 100000 ) .次の N 行のそれぞれには、1 つの M 桁の K-ary 番号が含まれています。数字は非減少順です。
インプリント
最初の行に必要な数を出力し (複数の解決策がある場合は、それらのいずれかを出力します)、2 行目には — を出力します。初日にテレビの司会者を指名するときに、賞金として支払わなければならない金額。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
10 3 2
1 3 100
000
000
001
010
100
100
100
100
110
111号
| 011
6 |
| 2 |
1 1 10
100
0 |
1
0 |