31586번 - Test Data Creation 스페셜 저지

문제

진우는 함수컵 예비소집에 나온 도시와 비트코인 문제를 보고 아래와 같은 코드로 문제를 풀었다.

#include <stdio.h>
int N, M, arr[301][301];
bool solve() {
 ... // 중략
}
int main() {
 scanf("%d%d", &N, &M);
 for(int i=0; i<N; i++) {
 for(int j=0; j<M; j++) {
 scanf("%d", &arr[i][j]);
 }
 }
 puts(solve() ? "Yes" : "No");
 return 0;
}

진우가 코드를 제출한 후 채점 결과를 기다렸다가 틀렸습니다 결과를 보고 충격을 받았다. 진우는 4시간 동안 '맞았는데 왜 틀리지?'를 중얼거리면서 고민하다가, $N$과 $M$을 반대로 입력했다는 것을 깨달았다. 결국 진우는 $N$과 $M$을 입력하는 부분만 바꿔서 맞았습니다!! 를 받았다.

이러는 진우를 본 명준이는 이 문제를 C모 사이트 대회에 내면 재미있겠다는 생각이 들었다. 명준이는 프리테스트(Pretest, 대회 도중에 제공하는 데이터)에는 약한 데이터만을 넣어두어서 진우가 틀린 코드를 냈을 때 맞았습니다!! 결과를 보고 방심했다가 시스템 테스트(Systest, 대회 이후에 추가로 채점하는 데이터)에서 결과가 바뀌는 것을 기대하고 있다.

명준이는 진우의 코드를 통과시키는 약한 데이터를 제작하려고 한다. 명준이는 우선 $N \times M$개의 격자 값을 모두 0으로 초기화했다. 이제 명준이는 격자의 일부 값을 1로 바꾸려는데 명준이의 컴퓨터는 별로 좋지 않기 때문에 각 격자의 값을 1로 바꾸는 데 좀 시간이 걸린다. $r$행 $c$열의 값을 1로 바꾸기 위해서는 $t_{r,c}$ 만큼의 시간이 필요하다.

명준이는 답이 No인 약한 데이터는 금방 만들었으나 답이 Yes인 약한 데이터는 만드는 데 너무 많은 시간이 걸린다. 어쩔 수 없이 명준이는 당신에게 도움을 요청했다! 명준이를 도와 약한 데이터를 최대한 빨리 만드는 프로그램을 작성하여라.

입력

첫 번째 줄에 데이터의 가로 크기 $N$과 세로 크기 $M$이 주어진다. (1ドル \le N, M \le 300$)

두 번째 줄부터 $M$개의 줄에는 각 격자의 값을 1로 바꾸는 데 걸리는 시간 $t_{r,c}$ (1ドル \le t_{r,c} \le 10,000円$)가 주어진다.

출력

첫 번째 줄에는 약한 데이터를 만드는 데 걸리는 시간의 최솟값을 출력한다.

두 번째 줄부터 $M$개의 줄에는 데이터를 나타내는 $N$개의 정수(0 또는 1)를 공백을 사이에 두고 출력한다. 이 데이터는 진우의 잘못된 코드와 정답 코드에서 모두 Yes가 나와야 한다.

만약 만들 수 있는 데이터가 여러 개라면 그중 아무거나 출력한다.

제한

힌트