საშობაო ტკბილეული

დროის ლიმიტი: 3 წმ

მეხსიერების ლიმიტი: 512 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout


შობაზე საჩუქრების დასარიგებლად სანტამ ყველაფერი მოამზადა გარდა თავისი მარხილისა. იმისათვის, რომ მარხილში ჩაბმულმა ირმებმა ძალა არ დაკარგონ, მათ სანტამ ტკბილეული უნდა მისცეს, რომლებიც ელფებმა დაუმზადეს საშობაოდ. სანტას უნდა, რომ ბავშვებისთვის რაც შეიძლება მეტი ტკბილეული დარჩეს, ამისათვის კი აინტერესებს მინიმალური რაოდენობა ტკბილეულისა, რაც შეიძლება ირმებს უწილადოს, რათა მათ შეძლონ ყველა ქალაქამდე ჩაღწევა და საჩუქრების დარიგება. ასევე სანტას სურს, რომ შეუმჩნევლად იფრინოს ქალაქების შორის - ამისათვის საჭიროა, რომ ის ყოველი ქალაქში ერთხელ ჩავიდეს და მხოლოდ ვერტიკალურად ან ჰორიზონტალურად გადაადგილდეს.

ქალაქების რუკა კი მოცემულია ორგანზომილებიანი ცხრილის სახით, სადაც წერია თუ რამდენად უყვართ ტკბილეული ამ ქალაქში(sweet[N][M] - სულ N*M ქალაქი). სანტას სურს, რომ დათვალოს მინიმალური რაოდენობა ტკბილეულისა, რაც ირმებს უნდა უწილადოს, რომ მან ყველა ქალაქი შეუმჩნევლად მოიაროს. შესაბამისად სანტას ნებისმიერი ქალაქიდან(sweet[i][j]) შეუძლია წავიდეს მხოლოდ იმ ქალაქებში, რომლებიც მიმდინარე ქალაქთან იზიარებენ ან ვერტიკალს ან ჰორიზონტალს. ტკბილეულის რაოდენობას რაც ირმებს სჭირდებათ, რომ ორ ქალაქს შორის მანძილი დაფარონ არის მოდული სხვაობებისა ტკბილეულის კოეფიციენტების ამ ორ ქალაქს(a და b) შორის: abs(sweet[i][a] - sweet[i][b]), abs(sweet[a][j] - sweet[b][j]) ან abs(sweet[i][a] - sweet[b][j]).

 

მონაცემთა შეზღუდვები:

* 1 ≤ N*M ≤ 100000

* 0 ≤ sweet[i][j] ≤ 1000000000

 

შესატანი მონაცემები:

სტრიქონი 1: ორი ჰარით გამოყოფილი მთელი: N და M.

N ცალი სტრიქონი - სადაც i-ური სტრიქონი შეიცავს M ცალ კოეფიციენტს(თუ რამდენად უყვართ ტკბილეული ამ ქალაქში(i,j)) ჰარით გამოყოფილს.

 

გამოსატანი მონაცემები:

სტრიქონი 1: მინიმალური რაოდენობა ტკბილეულისა, რაც სანტას შეუძლია რომ უწილადოს ირმებს.




მაგალითები

შესატანი მონაცემები
3 4 1 7 10 2 5 6 8 3 0 5 2 7 დაკოპირება
გამოსატანი მონაცემები
16 დაკოპირება
შესატანი მონაცემები
4 1 1 1 3 4 დაკოპირება
გამოსატანი მონაცემები
3 დაკოპირება
შესატანი მონაცემები
1 4 7 3 9 1 დაკოპირება
გამოსატანი მონაცემები
8 დაკოპირება