Karte

비토의 테이블 위에 $1$부터 $N$까지 번호가 적힌 빨간 카드 $N$장과 $1$부터 $M$까지 번호가 적힌 파란 카드 $M$장이 있다. 빨간 카드 $c$와 파란 카드 $p$의 쌍 $(c, p)$마다 COMBO 동작을 만들 수 있다.

카드 덱의 강도는 다음과 같이 정의한다.

강도 = (COMBO 동작 수) - $X$ $\times$ (빨간 카드 수) - $Y$ $\times$ (파란 카드 수)

여기서 COMBO 동작 수는 선택한 덱에 빨간 카드 $c$와 파란 카드 $p$가 모두 들어 있는 쌍 $(c, p)$의 개수이다. 비토는 테이블에 있는 카드를 아무거나 덱에 넣을 수 있다. 비토가 만들 수 있는 덱 중 강도가 가장 큰 값을 구하라. 빈 덱을 고르는 것도 가능하다.

첫 줄에 자연수 $N$, $M$, $X$, $Y$가 주어진다 ($1 \le N, M \le 21$, $0 \le X, Y \le 30$).

이어지는 $N$개의 줄에는 $M$개의 문자($0$ 또는 $1$)가 주어진다. $i$번째 줄의 $j$번째 문자가 $1$이면 $i$번째 빨간 카드와 $j$번째 파란 카드가 COMBO 동작을 만든다는 뜻이고, $0$이면 만들지 않는다.

비토가 만들 수 있는 가장 강한 덱의 강도를 한 줄에 출력한다.

첫 번째 예시: 비토는 테이블의 카드를 모두 고른다. 이때 COMBO 동작은 3개가 된다.

두 번째 예시: 비토는 처음 빨간 카드 2장과 파란 카드 3장을 모두 고른다. 이때 COMBO 동작은 6개가 된다. 빨간 카드를 2장 골랐으므로 COMBO 동작 수 6에서 $X \times 2 = 2$를 뺀 4가 덱의 강도이다.