포페알라

루마니아어 낱말 popeală는 역사 소설 "Alexandru Lăpușneanul"에서 왔다. 이 낱말은 최근 루마니아 프로그래밍 대회에서 다시 쓰이기 시작했고, 채점 위원회가 별난 방식으로, 대개는 의도치 않게 참가자를 힘들게 만드는 상황을 가리킨다. 지나치게 빡빡한 시간 제한, 망가진 테스트 데이터, 잘못 쓴 문제 설명, 키보드 빼앗기 같은 것이 여기에 해당한다. 이 문제도 그런 상황을 다룬다.

참가자가 $N$명인 대회가 있다. 문제는 하나뿐이고, 그 문제의 테스트 케이스는 $T$개다. 위원회는 이 테스트 케이스를 서브태스크로 묶으려고 한다.

서브태스크 규칙은 다음과 같다. 각 테스트 케이스는 정확히 하나의 서브태스크에 속한다. 서브태스크 하나에 들어가는 테스트 케이스의 개수에는 제한이 없지만, 빈 서브태스크는 만들 수 없다. 어떤 참가자가 한 서브태스크의 테스트 케이스 중 하나라도 틀리면 그 참가자가 그 서브태스크에서 받는 점수는 $0$이다. 하나도 틀리지 않으면 그 서브태스크에 속한 테스트 케이스의 배점을 모두 더한 점수를 받는다.

위원회는 대회가 끝난 뒤에 이 묶기를 한다. 누가 어떤 테스트 케이스를 맞혔는지 이미 알고 있으므로, 대회 전체에서 참가자들이 받는 점수의 합이 최소가 되도록 묶을 생각이다.

길이가 $T$인 배열 $\mathrm{Points}$가 주어진다. $\mathrm{Points}[i]$는 $i$번째 테스트 케이스의 배점이다. 크기가 $N \times T$인 행렬 $\mathrm{Results}$도 주어진다. $i$번째 참가자가 $j$번째 테스트 케이스를 맞혔으면 $\mathrm{Results}[i][j]$가 $1$, 아니면 $0$이다. 위원회는 서브태스크마다 번호가 연속인 테스트 케이스만 담기로 이미 정했다. 즉 테스트 케이스 $X$와 $Y$가 같은 서브태스크에 있으면, $X \le Z \le Y$인 모든 테스트 케이스 $Z$도 같은 서브태스크에 있다.

$1 \le K \le S$인 각 $K$에 대해, 테스트 케이스를 정확히 $K$개의 서브태스크로 묶을 때 대회 전체 점수 합의 최솟값을 구하라.

첫째 줄에 세 정수 $N$, $T$, $S$가 공백으로 구분되어 주어진다.

둘째 줄에 $T$개의 정수가 공백으로 구분되어 주어진다. $i$번째 수가 $\mathrm{Points}[i]$다.

다음 $N$개의 줄에 $0$과 $1$로 이루어진 길이 $T$의 문자열이 한 줄에 하나씩 주어진다. $i$번째 줄의 $j$번째 문자가 $\mathrm{Results}[i][j]$다.

• $1 \le T \le 20000$
• $1 \le N \le 50$
• $1 \le S \le \min(50, T)$
• $1 \le \mathrm{Points}[i] \le 10000$ ($1 \le i \le T$)
• $(\mathrm{Points}[1] + \mathrm{Points}[2] + \dots + \mathrm{Points}[T]) \times N \le 2 \times 10^9$

$S$개의 줄을 출력한다. $i$번째 줄에는 테스트 케이스를 정확히 $i$개의 서브태스크로 묶을 때 대회 전체에서 나올 수 있는 점수 합의 최솟값을 출력한다.

첫 번째 예제에서는 참가자가 $2$명, 테스트 케이스가 $3$개, $S = 3$이다. 따라서 서브태스크가 $1$개, $2$개, $3$개일 때의 최솟값을 차례로 구해야 한다. 배점은 $4$, $3$, $5$다.

서브태스크가 하나면 테스트 케이스 세 개가 모두 같은 서브태스크에 들어간다. 두 참가자 모두 하나씩 틀렸으므로 점수 합은 $0$이다.

서브태스크가 둘이면 묶는 방법이 두 가지다. 한쪽은 점수 합이 $12$, 다른 쪽은 $8$이므로 작은 쪽인 $8$을 고른다.

서브태스크가 셋이면 묶는 방법이 하나뿐이고, 이때 점수 합은 $16$이다.