Problem Review
InterviewTime limit2sMemory limit256 MB
Each of m problems must be reviewed in order by a jury member willing to review it; switching reviewers costs c seconds, so find the minimum total time.
- Level
Medium5 of 10
- Topics
- Dynamic programming, Implementation, Array, String
- Solved
- No attempts yet
Problem
The organizers of the final round of a programming contest face a hard task: scheduling all the events. The sponsors insist that their talks be as long as possible, so the problem review must take as little time as possible.
Along with the contestants, n jury members came to the contest, and for each of them it is known which of the m problems given to the contestants they want to review. Each jury member spends t seconds reviewing any problem. Switching from one jury member to another during the review takes c seconds. If the jury member conducting the review continues with the next problem, there is no loss of time.
Find the minimum time the review of all problems can take, given that the problems must be reviewed in order from the first to the m-th and each problem must be reviewed by some jury member who wants to review it.
Input
The first line contains the number of tests T. Then the descriptions of T tests follow.
The first line of a test contains the integers n, m, t, and c (1 ≤ n, m, t, c ≤ 100). Then n lines follow, each containing a string of m characters, 0 or 1. If the j-th character of the i-th line is 1, the i-th jury member wants to review the j-th problem; if it is 0, they do not. It is guaranteed that at least one person wants to review each problem.
The input file size does not exceed 2 megabytes.
Output
For each test, output a single number, the answer to the problem.