Республиканская олимпиада по информатике 2009 год

(Дене шынықтыру)

Ограничение по времени:

2 секунд

Ограничение по памяти:

256 мегабайт

Оқушылар арасында пәндер бойынша өтетін олимпиадалардың тізіміне дене шынықтыруды қосу шешілді. Оргкомитет жүру бойынша өтетін жарысқа маршрутты дайындауы тиіс. Жарысты ұйымдастыру үшін шаршыларға бөлінген $N \times M$ болатын тіктөртбұрышты территория бөлінді. Әр шаршы үшін оның жарыстарға дайындау бағасы анықталды. Оған қоса, қатысушылардың маршруты бастала және аяқтала алатын шаршылар белгілі. Маршрут деп әр екі көрші шаршының ортақ қабырғасы бар шаршылар тізбегін атайық. Сіздің мақсатыңыз — оргкомитетке маршрутты дайындау бағасы минимал болатындай етіп таңдауға көмектесу.

Формат входного файла

Енгізу файлының бірінші жолында үш сан берілген: $N$, $M$ ($1 \le N, M \le 200$), онда $N$, $M$ — территорияның өлшемі. Келесі $N$ жолдың әрқайсысы $1$-ден $100$-ге дейінгі $M$ бүтін саннан — сәйкесінше шаршының жарысқа дайындау бағасы тұрады. Келесі жол $2$ бүтін саннан — маршрут басталуы тиіс шаршының жолы мен қатарының нөмірлері. Келесі жол $2$ бүтін саннан — маршрут аяқталуы тиіс шаршының жолы мен қатарының нөмірлері. Ешқандай шаршы маршруттың басы және аяғы бола алмайды. Жолдағы сандар бос жолмен бөлінген.

Формат выходного файла

Шығыс файлының бірінші жолында дайындау бағасы ең азын, ал келесі жолдарда маршрут картасын шығар. Маршурт картасы — $N \times M$ таблица. $i$-шы жолдың $j$-ші қатарында $0$, егер осы шаршы бойынша маршрут өтпесе немесе $1$, егер осы шаршы бойынша маршрут өтсе. Егер оптималды жауаптар саны бірнеше болса, кез-келгенін шығар. Жолдағы сандар бос жолмен бөліну керек.

Пример:

Вход

3 3
1 1 1
1 1 1
10 1 1
1 1
3 3

Ответ

5
1 0 0
1 1 0
0 1 1