外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

N - Cat and cat

作成者 nekooooooo、siooisi、jammy、trueryob

テスター jammy、siooisi、tau0529、trueryob

配点 425 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

問題文

NN 個の文字列 S1,S2,…,SNS_1, S_2, \dots, S_N が与えられます。
わりとねこくんは、これらすべての文字列を元の文字列 S1,S2,…,SNS_1, S_2, \dots, S_N のうちのいずれか 11 つと完全に一致させたいと考えています。

最初、わりとねこくんはいずれの文字列の編集画面も開いていません。
わりとねこくんはコストを支払うことで、以下の 22 種類の操作を好きな順序で好きな回数行うことができます。

  1. 画面の移動: コスト xx を支払う。任意の文字列 SiS_i (1≤i≤N1 \le i \le N) を 11 つ選び、その文字列の編集画面に移動する。
  2. 文字の編集: コスト yy を支払う。現在開いている文字列に対して、以下のいずれかの操作を 11 回行う。
    • 好きな位置に英小文字を 11 文字挿入する。
    • 好きな位置の文字を 11 文字削除する。
    • 好きな位置の文字を別の英小文字に変更する。

適切な操作を行い、すべての文字列を元の NN 個の文字列のいずれか 11 つと同じ文字列にするために必要な合計コストの最小値を求めてください。

制約

  • 2≤N≤1002 \le N \le 100
  • 1≤x,y≤1091 \le x, y \le 10^9
  • SiS_i は英小文字のみからなる長さ 11 以上の文字列
  • ∑i=1N∣Si∣≤2000\sum_{i=1}^N |S_i| \le 2000
  • N,x,yN, x, y は整数

入力

入力は以下の形式で標準入力から与えられます。

NxyN \quad x \quad y S1S_1 S2S_2 ⋮\vdots SNS_N

出力

必要な合計コストの最小値を 11 行に出力してください。

入力例 1

4 2 3
cat
cats
cut
at

出力例 1

15

すべての文字列を S1S_1 と同じ cat に揃えることを考えます。

  1. S2S_2 の編集画面に移動します。
  2. S2S_2 の 44 文字目の s を削除します。cats は cat になります。
  3. S3S_3 の編集画面に移動します。
  4. S3S_3 の 22 文字目の u を a に変更します。cut は cat になります。
  5. S4S_4 の編集画面に移動します。
  6. S4S_4 の先頭に c を挿入します。at は cat になります。

画面の移動と文字の編集をそれぞれ 33 回行ったので、合計コストは 3×2+3×3=153 \times 2 + 3 \times 3 = 15 です。 元の 44 個の文字列はすべて異なるため、どれに揃える場合も少なくとも 33 個の文字列を編集する必要があります。したがって、1515 が最小です。

入力例 2

3 9 8
neko
neko
neko

出力例 2

0

最初からすべての文字列が一致しているので、操作は不要です。

入力例 3

6 3 1
aaaa
aaaa
aaab
aabb
abbb
bbbb

出力例 3

22

参加受付は終了しました。