Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: hvkirtimas.in

Rezultatų failas: hvkirtimas.out

Jei norite pateikti savo sprendimą - prisijunkite.

HV Kirtimas

Žinomas toks matricos M sunaikinimo metodas:

  1. pasirenkamas bet koks matricos elementas b_i=a_{i,j} (dėl patogumo renkamės elementą iš eilutės, kurios numeris sutampa su algoritmo iteracijos numeriu - i);
  2. iš matricos horizontaliai iškertamas stulpelis (jis lieka matricoje, tačiau jo rinktis nebegalima), kurio numeris yra j;
  3. iš matricos vertikaliai iškertama eilutė, kurios numeris yra i;
  4. jei matrica nėra tuščia (joje yra dar neiškirstų elementų), einama į žingsnį 1.

Tokio naikinimo kaina apibrėžiama kaip:

m=\\sum_{i=1}^{N}b_i

Jums reikės rasti mažiausią matricos naikinimo kainą.

Pradiniai duomenys

Pirmojoje pradinių duomenų eilutėje nurodomas skaičius N (1\\leqN\\leq200), nusakantis matricos dydį. Likusiose N eilučių nurodomi elementai, sudarantys matricą, t.y. i'tojoje pateikiama N elementų a_{i,1},a_{i,2},\\ldots,a_{i,N} (1\\leqa_{i,j}\\leq1000).

Rezultatai

Pirmoje rezultatų eilutėje turi būti pateiktas skaičius m, nurodantis minimalią matricos sunaikinimo kainą. Kitoje eilutėje reikia nurodyti elementus 1\\leqc_i\\leqN, kuriuos reikia pasiimti siekiant gauti minimalią kainą. Elementai nurodomi jų stulpelio numeriu pradedant elementu esančiu pirmojoje eilutėje ir baigiant elementu paskutiniojoje eilutėje.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
4
952 174 746 376
144 221 522 181
660 549 992 258
480 983 721 733
 
1297
2 1 4 3