Birləşmə Arzusu#6654
Acme Konsaltinq Qrupu sizi dinamizmi, sinerjiyanı və davamlılığı artırmaq üçün yeni texnologiya parkına göndərib. Bu terminlərin mənasını tam bilməsəniz də, pul qazanmaqda bacarıqlısınız və bunu etməyi planlaşdırırsınız. Park 3×n ölçüsündə obyektlərdən ibarətdir. Hər bir obyektin içində bir startap yerləşir və onun daxili dəyəri var. Siz qonşu startaplar arasında birləşmələri asanlaşdıraraq, onların dəyərini artırmaq və beləliklə, öz latte və burrito mağazalarınızın zəncirini açmaq arzunuzu həyata keçirmək istəyirsiniz.
Anti-inhisar qanunlarına görə, hər bir fərdi birləşmə yalnız iki startapı əhatə edə bilər və heç bir startap bir dəfədən çox birləşmədə iştirak edə bilməz. Bundan əlavə, iki startap yalnız qonşu obyektlərdə yerləşdikdə birləşə bilər (diagonal nəzərə alınmır). Birləşmədən əldə olunan əlavə dəyər, iştirak edən iki startapın dəyərlərinin hasilinə bərabərdir. Hər hansı bir startapı birləşməyə daxil etməmək seçiminiz var, bu halda heç bir əlavə dəyər yaranmır. Məqsədiniz, ən böyük ümumi əlavə dəyəri yaradan birləşmələr dəstini tapmaqdır. Məsələn, soldakı şəkildə göstərilən startap dəyərləri, sağdakı şəkildə göstərildiyi kimi optimal şəkildə birləşdirilə bilər və ümumi əlavə dəyər 171 olar.
Hər bir test halının ilk sətri obyektlər şəbəkəsinin enini göstərən n ≤ 1000 müsbət tam ədədi ehtiva edəcək. Bundan sonra üç sətir gəlir, hər biri n müsbət tam ədəd (hamısı ≤ 100) ehtiva edir və hər bir startapın dəyərini təmsil edir. Tək 0 ehtiva edən bir sətir girişi bitirəcək.
Hər bir test halı üçün, həmin startap dəsti üçün birləşmələr vasitəsilə əldə edilə bilən maksimum əlavə dəyəri çıxarın.
Nümunə 1