약한 데이터 만들기

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

#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$을 올바르게 읽도록 했고, 맞았습니다!! 를 받았다.

이를 본 명준이는 이 문제를 다른 사이트의 대회에 내면 재미있겠다고 생각했다. 명준이는 대회 중에 공개하는 프리테스트(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가 나와야 한다.

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