| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 39 | 14 | 14 | 37.838% |
On Vito’s table, there are $N$ red cards labeled with numbers from 1ドル$ to $N$ and $M$ blue cards labeled with numbers from 1ドル$ to $M$. Each pair of red and blue cards $(c, p)$ (where $c$ represents a red card and $p$ a blue card) can create a COMBO move.
The strength of a deck of cards is defined as:
strength = (number of COMBO moves) - $X$ · (number of red cards) − $Y$ · (number of blue cards)
where the number of COMBO moves is the number of pairs $(c, p)$ such that the red card $c$ and the blue card $p$ are in the chosen deck. Vito can include any card from the table in his deck. Help Vito find the value of the strongest deck he can build. Vito can also choose an empty deck of cards.
The first line contains 4ドル$ natural numbers $N,ドル $M,ドル $X,ドル $Y$ (1ドル ≤ N, M ≤ 21,ドル 0ドル ≤ X, Y ≤ 30$).
In the next $N$ lines, there is a sequence of $$M characters (0ドル$ or 1ドル$), where the $j$-th character indicates whether the $i$-th red card and the $j$-th blue card create a COMBO move.
In the first and only line, output the value of the strongest deck of cards that Vito can build.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 18 | $Y = 0$ |
| 2 | 11 | 1ドル ≤ N, M ≤ 9$ |
| 3 | 24 | 1ドル ≤ N, M ≤ 15$ |
| 4 | 17 | No additional constraints. |
2 2 0 0 11 10
3
3 3 1 0 111 111 000
4
3 3 1 1 111 101 011
1
Explanation of the first sample case: Vito will choose all the cards from the table, creating 3ドル$ COMBO moves.
Explanation of the second sample case: Vito will select the first 2ドル$ red cards and all 3ドル$ blue cards, creating 6ドル$ COMBO moves. The deck strength is 4ドル$ because Vito selected $2ドル red cards, so the number of COMBO moves, i.e., 6ドル,ドル is reduced by 2ドル$.