def rec(i, j, m)
  return $memo[i][j][m] if $memo[i][j][m] != 1e10

  res = 1e10
  return 0 if i+1 >= $stone.size
  for jj in 0...$stone[i+1].size do
    add = ($stone[i][j][1]+$stone[i+1][jj][1])*($stone[i][j][0]-$stone[i+1][jj][0]).abs
    res = [res, rec(i+1, jj, m)+add].min
  end

  return $memo[i][j][m] = res if (i+2 >= $stone.size) || (m < 1)
  for jj in 0...$stone[i+2].size do
    add = ($stone[i][j][1]+$stone[i+2][jj][1])*($stone[i][j][0]-$stone[i+2][jj][0]).abs
    res = [res, rec(i+2, jj, m-1)+add].min
  end

  return $memo[i][j][m] = res
end

while true do
  n, m = gets.split.map(&:to_i)
  break if n | m == 0
  $stone = []
  n.times do
    line = gets.split.map(&:to_i)
    $stone.push(Array.new(line.shift) {line.shift(2)})
  end
  $memo = Array.new(n-1) {Array.new(1001) {Array.new(m+1, 1e10)}}
  2.times {$memo.push(Array.new(1001) {Array.new(m+1, 0)})}

  res = 1e10
  for j in 0...$stone[0].size do
    res = [res, rec(0, j, m)].min
  end
  for j in 0...$stone[1].size do
    break if m == 0
    res = [res, rec(1, j, m-1)].min
  end
  puts res
end