Kaubanduskeskus

Linna ehitatakse uut kaubanduskeskust, mille põhiplaan koosneb $N \times M$ ühikruudust. Ruut $(1, 1)$ on keskuse loodenurgas ja ruut $(N, M)$ kagunurgas. Kuigi keskust alles ehitatakse, on turundajad juba hinnanud, et ruutu $(i, j)$ hakkab päevas külastama $A_{ij}$ ostjat.

Keskuses tahavad oma poed avada $K$ firmat, mis on nummerdatud $1 \ldots K$. Iga pood võib paikneda ühes või mitmes ruudus, aga peab olema 4-sidus: poe igast ruudust peab pääsema poe igasse teise ruutu, läbides teel ainult selle poe ruute ja astudes igal sammul ühest ruudust teise üle nende ühise serva. Loomulikult ei saa ühes ruudus olla mitut poodi. Lisaks ei luba ohutusnõuded teha keskusse poodi, mis on suurem kui $S$ ruutu.

Kaubanduskeskuse juhataja tahab pakkuda poodidele pindu nii, et nende alla jäävate ruutude külastatavuste summa oleks võimalikult suur (vähemkülastatavad ruudud jäävad koridorideks ja muudeks abiruumideks). Aita turundusjuhil koostada võimalikult hea pakkumine.

Sisendfaili esimesel real on testi number $T$.

Faili teisel real on neli täisarvu $N$, $M$, $K$ ja $S$: keskuse laius ja pikkus, poodide arv ja poe maksimaalne suurus.

Järgmisel $N$ real on igaühel täpselt $M$ täisarvu $A_{ij}$: keskuse ruutude külastatavused.

Faili viimasel real on täisarv $Y$: poodide summaarne külastatavus žürii lahenduses.

Väljundfaili esimesele reale väljastada testi number $T$.

Järgmisele $N$ reale väljastada igaühele täpselt $M$ täisarvu $B_{ij}$ ($0 \le B_{ij} \le K$), kus $B_{ij} > 0$ näitab vastaval ruudul asuva poe omaniku numbrit ja $B_{ij} = 0$ tähistab vabaks jäävat ruutu.