ぴょんぴょん

pyonpyon

# AOJ 0530

eval(
   %(                             I=1/0.0; loop{n,
   m                       =gets.s        p lit.m ap
  (                  &:  to_i);n<1&&exit;c=Arr      ay.new(n
 )   {              Ha sh[[*gets.split[1..-1].map(  &:t  o
_    i)             .each_slice(2)]]};p=Array.new(m+ 1){|k|n.ti
mes.map{|i|       Hash[c[i].map{|j,_|[j,((i<1||i<2&   &k>1)    ?
      0:I)]}]}};0.upto(m){|k|1.upto(n-1){|i|c[i].ma    p{|j,    d
|        y=p[k][i];f=->k,i{c[i].map{|l,e|a=p[k][i][l]   +(d+e   )
 *(j-l).abs;y[j]>a&&y[j]=a  }};f[k,i-1];k>0 &&i>1&&f    [k-1,i   -
    2]}}};x=I;0.upto(m){|  k|d=p[k];(d[-1]  .merge(k     !=(m)?  d[
   -2]  :{})).map{|_,v|x  >v&&x= v}};p(x)}  ).split()    .join)  #
  ###  ###############   ######  ########   ### ########   ####   ##
  ##  ###############     ####  ########    ##  ########## ####    #
   #################   ###       ######     ##  ##########  ##    #
    ######### ######  #  ###           #####    ##########       ###
     ####### #######    ## #          # ###### ###########    ###   ########
     ######  #######   ## #            #### #  ###############              ##
      ####   ########   ##             ##  ## ###############
       #### #########                   #### #################################
   #  ##  ###########                      #########################
    ##   ########### #        ####     ########################## ###
         ##  ####     ##      #   #    ##########################  ###
         ## ###       ####     ###    ##########################   ###
           ##         #######        ### #####################  #####
            ##        ###    ##########  ### ####  ######  #####
                     ##               ##########   ####  ###
                                       ####  ##     ##     ##
                                         ##  ##      ##
                                          ##