문제 해설
면접 대비시간 제한2초메모리 제한256 MB
m개의 문제를 순서대로 검토하며, 각 문제를 검토하려는 심사위원이 맡아야 하고 심사위원이 바뀔 때마다 c초가 추가로 든다. 전체 검토 시간의 최솟값을 구한다.
문제
한 프로그래밍 대회 결선 단계의 주최자들은 모든 행사를 계획해야 하는 어려운 과제를 안고 있다. 스폰서들은 자신들의 발표가 최대한 길어지기를 원하므로, 문제 해설에 걸리는 시간을 최소화해야 한다.
대회에는 참가자들과 함께 n명의 심사위원이 왔고, 각 심사위원이 참가자들에게 제시된 m개 문제 중 어떤 문제를 해설하고 싶어 하는지 알려져 있다. 각 심사위원은 어떤 문제를 해설하든 t초를 쓴다. 해설 도중 다른 심사위원으로 교체되는 데는 c초가 걸린다. 만약 해설을 맡은 심사위원이 다음 문제도 계속 해설한다면 시간 손실은 없다.
문제가 1번부터 m번까지 순서대로 해설되어야 하고, 각 문제를 해당 문제를 해설하고 싶어 하는 심사위원 중 누군가가 반드시 해설해야 할 때, 모든 문제 해설에 걸릴 수 있는 최소 시간을 구하라.
입력
첫 줄에는 테스트의 수 T가 주어진다. 이어서 T개의 테스트가 주어진다.
각 테스트의 첫 줄에는 정수 n, m, t, c가 주어진다 (1 ≤ n, m, t, c ≤ 100). 이어서 n개의 줄에 0 또는 1로 이루어진 길이 m의 문자열이 주어진다. i번째 줄의 j번째 문자가 1이면 i번째 심사위원이 j번째 문제를 해설하고 싶어 한다는 뜻이고, 0이면 그렇지 않다는 뜻이다. 각 문제를 적어도 한 명은 해설하고 싶어 한다고 보장된다.
입력 파일의 크기는 2메가바이트를 넘지 않는다.
출력
각 테스트에 대해 답을 하나씩 출력한다.