INF = 1<<29
def solve(jump, i)
  to = (jump == 1) ? i + 1 : i + 2
  (jump == 1 ? $m + 1 : $m).times do |j|
    cnt = (jump == 1) ? j : j + 1
    $s[i].each do |x0, d0|
      $s[to].each do |x1, d1|
        v = i == 0 ? 0 : $dp[i][j][x0] + (x0 - x1).abs * (d0 + d1)
        $dp[to][cnt][x1] = v if $dp[to][cnt][x1] > v
      end
    end
  end
end
 
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|
    solve(1, i)
    break if i == n - 1
    solve(2, i)
  end
  p [*$dp[n-1][0,$m].flatten , *$dp[n][$m].flatten].min
end