SPOJ in Armenian

Ռադիոլոկացիոն կայանը (ՌԼԿ) բացկացած է մի քանի հաղորդիչներից (5-ից ոչ ավել)։ Դրանք չի կարելի իրար մոտ դնել. այդ դեպքում մեկը մյուսին կխանգարի։ Յուրաքանչյուր հաղորդիչ բաղկացած է քառակուսի մոդուլներից, որոնք իրար կից են դրվում։

Տրված է տեղանքի քարտեզը, որտեղ տեղադրված է կայանը։ Ամբողջ քարտեզը հարմարության համար բաժանված է վանդակների, և յուրաքանչյուր վանդակի համար հայտնի է, նրանում ՌԼԿ-ի հաղորդիչներից որևէ մեկի մոդուլ կա, թե ոչ։

Պահանջվում է ցանկապատել (մեկ կամ մի քանի ցանկապատով) ՌԼԿ-ի բոլոր հաղորդիչներն այնպես, որ ցանկապատի (կամ ցանկապատերի) երկարությունը լինի մինիմալ։ Ցանկապատը կամայական բեկյալ է։ Պարտադիր չէ, որ այն անցնի միայն վանդակների եզրերով։ Մի ցանկապատով կարելի է միանգամից մի քանի հաղորդիչ շրջափակել։

Մուտքը

Առաջին տողում տրված են N և M (1≤N≤20, 1≤M≤20) թվերը, որոնք սահմանում են տեղանքի չափերը։ Ապա տրված է N տող, յուրաքանչյուրում՝ M թիվ, 0, եթե այդ վանդակում հաղորդիչի մոդուլ չկա, և 1, եթե այդ վանդակում կա հաղորդիչի մոդուլ։

Հաղորդիչների ընդհանուր քանակը չի գերազանցում 5-ը։ Յուրաքանչյուր հաղորդիչ մոդուլների կապակցված խումբ է։ Երկու մոդուլ կոչվում են կապակցված, եթե նրանք տեղադրված են ընդհանուր եզր ունեցող վանդակներում, կամ կապված են իրար հետ ուրիշ մոդուլների միջոցով։ Մոդուլների քանակի վրա սահմանափակում չկա։

Ելքը

Ելքում պետք է արտածել մի թիվ՝ ցանկապատի մինիմալ հնարավոր երկարությունը ստորակետից հետո երեք նիշով։

Օրինակ

Մուտքը.
9 10
0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 1 1 0
1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0

Ելքը.
26.893

 
Կայանը կազմված է 5 հաղորդիչներից։
Վերևի՝ չորս մոդուլներից բաղկացած հաղորդիչը շրջափակող ցանկապատի երկարությունը 9.236 է։
Ներքևի ձախ անկյունում գտնվող երկու հաղորդիչները շրջափակված են մի ցանկապատով, որի երկարությունը 6.828 է,
իսկ ներքևի աջ անկյունում գտնվող երկու հաղորդիչները շրջափակված են 10.828 երկարությամբ մի ընդհանուր ցանկապատով։