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 } ]

  c = s.flatten(1).transpose[0].max

  dp = (n+1).times.map { (m+1).times.map { [INF] * (c+1) } }
  (m+1).times{ |i| dp[0][i].fill(0) }

  n.times do |i|
    (m+1).times do |j|
      s[i].each do |k, d0|
        s[i+1].each do |l, d1|
          x = i == 0 ? 0 : dp[i][j][k] + (l - k).abs * (d0 + d1)
          dp[i+1][j][l] = x if dp[i+1][j][l] > x
        end
      end
    end
    next if i == n - 1
    m.times do |j|
      s[i].each do |k, d0|
        s[i+2].each do |l, d1|
          x = i == 0 ? 0 : dp[i][j][k] + (l - k).abs * (d0 + d1)
          dp[i+2][j+1][l] = x if dp[i+2][j+1][l] > x
        end
      end
    end
  end
  min = dp[n][m].flatten.min
  m.times do |i|
    min = [dp[n-1][i].flatten.min, min].min
  end
  p min
end