C - Offline Gathering

配点 : $400$ 点
　　

問題文

動画配信者のSさんは、日付 $1,2,\ldots,N$ のうちからどれか $1$ 日を選んでオフ会を開くことにしました。

Sさんの動画の視聴者は全部で $M$ 人おり、それぞれの視聴者の予定を表す $M$ 行 $N$ 列のグリッド $T$ が与えられます。

$T$ の $i$ 行 $j$ 列の要素 $T_{i,j}$ は $i$ 人目の視聴者の日付 $j$ の予定を表しており、$T_{i,j}$ が o ならば $i$ 人目の視聴者は日付 $j$ にオフ会が開かれるなら参加する予定であり、 x ならば参加しない予定です。

あなたは $K$ 円の予算を持っており、予算が足りる限り以下の $2$ つの行動を何回でも行うことが出来ます。

• $A$ 円支払い、$2$ つの正整数 $x,y(1 \leq x \leq M,1 \leq y \leq N)$ を選び、 $x$ 人目の視聴者の日付 $y$ の予定を x にする。
• $B$ 円支払い、正整数 $x(1 \leq x \leq M)$ を選び、 $x$ 人目の視聴者の予定を全て x にする。

あなたが行動を終えた後、Sさんは参加者が最も多くなるような日付を選びオフ会を開きます。うまく行動を選んだときのオフ会の参加者の最小値を求めてください。

制約

• $1 \leq N \leq 500$
• $1 \leq M \leq 12$
• $1 \leq K \leq 10^9$
• $1 \leq A \leq B \leq 10^9$
• $T_{i,j}$ は o か x
• $T_{i,j}$ 以外の入力は全て整数 　　

入力

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

出力

答えを出力してください。

入力例1

3 4 5 1 2
ooo
oxo
xoo
ooo

出力例1

1

以下のような手順でオフ会の参加者の人数を $1$ 人に出来ます。

• $2$ 円支払い、$1$ 人目の視聴者の予定を全て x にする。残り予算は $3$ 円となる。
• $2$ 円支払い、$4$ 人目の視聴者の予定を全て x にする。残り予算は $1$ 円となる。
• $1$ 円支払い、$3$ 人目の視聴者の $3$ 日目の予定を x にする。残り予算は $0$ 円となる。

行動を終えた後、視聴者の予定は以下のようになります。

xxx
oxo
xox
xxx

Sさんがどの日付を選んでも参加者は $1$ 人です。参加者を $0$ 人にすることは出来ないので、 $1$ が答えです。

入力例2

8 11 20 1 4
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx

出力例2

0

そもそも最初から誰一人オフ会に参加する気がありません。一体何がダメだったんでしょうか。