Разбор задач

Перед организаторами финального этапа одного соревнования по программированию стоит сложная задача: спланировать все мероприятия. Спонсоры настаивают, чтобы их выступления были как можно длиннее, поэтому необходимо, чтобы разбор задач занял как можно меньше времени.

Вместе с участниками, на соревнования приехало n членов жюри, про каждого из которых известно, какие из предложенных участникам m задач он хочет разобрать. Каждый член жюри тратит на разбор любой задачи t секунд. На то, чтобы один из членов жюри сменил во время разбора другого, тратится c секунд. Если же проводящий разбор член жюри продолжает разбирать и следующую задачу, то потери времени нет.

Определите, какое наименьшее время может идти разбор всех задач, если задачи должны разбираться по порядку от первой до m-й и каждую задачу должен разбирать кто-либо из членов жюри, кто хочет ее разбирать.

В первой строке задано число T — число тестов. Далее идёт описание T тестов.

В первой строке теста заданы целые числа n, m, t и c (1 ≤ n, m, t, c ≤ 100). Далее, в n строках заданы строки из m символов 0 или 1, если j-й символ i-й строки равен 1, это значит, что i-й член жюри хочет разбирать j-ю задачу, а если он равен 0, то не хочет. Гарантируется, что каждую задачу хотя бы кто-то хочет разбирать.

Размер входного файла не превышает 2 мегабайт.

Для каждого теста выведите единственное число — ответ на задачу.