#!/usr/local/bin/ruby
class PriorityQueue
def initialize(n,c)
@n,@c,@cost = n,c,[]
@blen = (c+1).to_s(2).length+2
@size = Array.new(@blen+1){|i| 1<<(i-2)}
@size[0],@size[1],@size[@blen]=:no_size,1,n*c+1
@bucket = Array.new(@blen+1){[]}
@bucket[0]=[:not_reached]
@u = Array.new(@blen+1){|i| (1<<(i-1))-1}
@u[@blen]=n*c+1
end
def insert(v,vcost,idx=@blen)
idx.downto(0) do |i|
if @u[i] < vcost
@bucket[i+1] << v
@cost[v]=vcost
return
end
end
end
def decrease(v,vcost,idx=@blen)
oldcost = @cost[v]
idx.downto(1) do |i|
if @u[i] < oldcost
@bucket[i+1].delete(v)
insert(v,newcost,i+1)
@cost[v]=newcost
break
end
end
end
def delete_min
if @bucket[1].empty?.!
return @bucket[1].shift
end
min_pos,min_vector=nil,nil
2.upto(@blen) do |i|
current_bucket = @bucket[i]
if current_bucket.empty?.!
min_pos = i
minv,j = current_bucket[0],0
current_bucket[1..].each_with_index do |w,k|
if @cost[minv] > @cost[w]
minv,j = w,k+1
end
end
current_bucket.delete_at(j)
min_vector=minv
break
end
end
@u[0],@u[1]=@cost[min_vector]-1,@cost[min_vector]
2.upto(min_pos-1) do |i|
@u[i]=[@u[i-1]+@size[i],@u[min_pos]].min
end
while @bucket[min_pos].empty?.!
w = @bucket[min_pos].shift
insert(w,@cost[w],min_pos)
end
STDERR.puts "#{__method__}: min_vector: #{min_vector}" if $debug
min_vector
end
def cost(v); @cost[v]; end
end
class Jinarashi
def initialize(h,w,costs,digit=100)
@h,@w,@priorityqueue,@digit = h,w,nil,digit
@a = costs || Array.new(h){Array.new(w)}
end
def kinbou(idx)
w,h = idx%@digit,idx/@digit
arr = []
arr << @digit*(h-1)+w if 0<h
arr << @digit*(h+1)+w if h<@h-1
arr << @digit*h+w-1 if 0<w
arr << @digit*h+w+1 if w<@w-1
arr
end
def find_corner_by_dijkstra(h,w)
start_vertex = @digit*h+w
runset = (0...@h).map{|i|(0...@w).map{|j| @digit*i+j}}.flatten
res = [[@h-1,0],[@h-1,@w-1],[0,@w-1]].map{|i,j| @digit*i+j}
res1 = res.dup
@priorityqueue = PriorityQueue.new(@h*@w,@a.flatten.max)
@priorityqueue.insert(start_vertex,0)
while res.size > 0
point = @priorityqueue.delete_min
ridx = runset.bsearch_index{_1>=point}
runset.delete_at(ridx) #point is scanned.
res.delete(point)
kinbou(point).each do |idx|
if runset.bsearch{_1>=idx} == idx
y,x = idx%@digit,idx/@digit
newcost = @a[x][y]+@priorityqueue.cost(point)
if @priorityqueue.cost(idx).nil?
@priorityqueue.insert(idx,newcost)
elsif @priorityqueue.cost(idx)>newcost
@priorityqueue.decrease(idx,newcost)
end
end
end
end
res1.map{|idx| @priorityqueue.cost(idx)}.sum+@a[h][w]
end
def find_keiro
distance = @a[-1].sum+@a.map{|b| b[-1]}.sum
0.upto(@h-1) do |i|
0.upto(@w-1) do |j|
distance = [distance,find_corner_by_dijkstra(i,j)].min
end
end
distance
end
end
h,w = gets.split(" ").map(&:to_i)
arr = Array.new(h){gets.split(" ").map(&:to_i)}
g = Jinarashi.new(h,w,arr)
val = g.find_keiro
puts val
exit 0