INF = 1<<29
loop do
  n, m = gets.split.map(&:to_i)
  break if n == 0
  s = [[[0, 0]], *n.times.map { gets.split.map(&:to_i)[1..-1].each_slice(2).to_a } ]
  ss = s.flatten(1).transpose[0]
  ss.sort!.uniq!
  s_index = (n+1).times.map{ [] }
  (n+1).times do |i|
    s[i].each do |x, _|
      s_index[i] << ss.index(x)
    end
  end

  dp = (n+1).times.map { (m+1).times.map { [INF] * ss.size } }

  (m+1).times{ |i| dp[0][i].fill(0) }
  n.times do |i|
    (m+1).times do |j|
      s[i].each_with_index do |(x0, d0), k|
        s[i+1].each_with_index do |(x1, d1), l|
          v = i == 0 ? 0 : dp[i][j][s_index[i][k]] + (x0 - x1).abs * (d0 + d1)
          dp[i+1][j][s_index[i+1][l]] = v if dp[i+1][j][s_index[i+1][l]] > v
        end
      end
    end
    next if i == n - 1
    m.times do |j|
      s[i].each_with_index do |(x0, d0), k|
        s[i+2].each_with_index do |(x1, d1), l|
          v = i == 0 ? 0 : dp[i][j][s_index[i][k]] + (x0 - x1).abs * (d0 + d1)
          dp[i+2][j+1][s_index[i+2][l]] = v if dp[i+2][j+1][s_index[i+2][l]] > v
        end
      end
    end
  end
  p [*dp[n-1][0,m].flatten , *dp[n][m].flatten].min
end