| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 38 | 13 | 13 | 36.111% |
Перед организаторами финального этапа одного соревнования по программированию стоит сложная задача: спланировать все мероприятия. Спонсоры настаивают, чтобы их выступления были как можно длиннее, поэтому необходимо, чтобы разбор задач занял как можно меньше времени.
Вместе с участниками, на соревнования приехало 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 мегабайт.
Для каждого теста выведите единственное число — ответ на задачу.
3 3 3 60 20 110 011 101 2 2 60 20 11 00 3 3 60 20 101 010 101
200 120 220
Contest > Russian Code Cup > 2014 > RCC 2014 Elimination Round A번