Մատրիցի վանդակների S ենթաբազմությունը կանվանենք կապակցված, եթե գոյություն ունի այդ ենթաբազմությանը պատկանող ցանկացած վանդակից ցանկացած այլ վանդակ տանող ճանապարհ ։ Իսկ ճանապարհ ասելով, կհասկանանք վանդակների այնպիսի հաջորդականություն, որտեղ բոլոր երկու հարևան i=1…k-1, տարրերն ընդհանուր կողմ ունեն։
Տրված է N տողերից և M սյուներից կազմված A մատրիցը։ A մատրիցին պատկանող S կապակցված ենթաբազմության համար սահմանենք կշիռ հետևյալ կերպ․
Որտեղ |S|-ը ցույց է տալիս S ենթաբազմության տարրերի քանակը, իսկ A(t)-ն մատրից t տարրի արժեքն է։
Մուտքային տվյալներ
Առաջին տողում տրված են մատրից N և M(1 ≤ N, M ≤ 1000) չափերը։
Հաջոր N տողերից յուրաքանչուրում տրված են M ոչ բացասական ամբողջ թվեր՝ մատրիցի A[i][j] տարրերը։
Ելքային տվյալներ
Արտածեք մեկ թիվ՝ տրված մատրիցի բոլոր հնարավոր S կապակացված ենթաբազմություններից մեծագույն կշիռ ունեցողի weight(S) կշիռը։
Դիտարկենք {(0,0), (0,1), (1,1)} կապակցված ենթաբազմությունը կամ {(0,0), (1,0),(1,1)} կապակցված ենթաբազմությունը։ Նրանց երկուսի կշիռն էլ 3 է։ Ավելի մեծ կշռով կապակցված ենթաբազմություն այս օրինակում գոյություն չունի։