### constant

MAX_INT = 1 << 30

### main

loop do
  n, m = gets.strip.split(' ').map{|s| s.to_i}
  break if (n | m) == 0

  ystones = n.times.map{[]}

  for y in (0...n)
    ks = gets.strip.split(' ').map{|s| s.to_i}
    k = ks.shift
    for i in (0...k)
      ystones[y] << [ks[2 * i], ks[2 * i + 1]]
    end
  end
  #p stones
  #p max_x

  dists = (n + 1).times.map{(m + 1).times.map{10.times.map{MAX_INT}}}

  dists[0][m] = 10.times.map{0}

  if m > 0
    dists[1][m - 1] = 10.times.map{0}
  end

  for y in (0...(n - 1))
    ysts0 = ystones[y]
    ysts1 = ystones[y + 1]
    ysts2 = ystones[y + 2]

    for m0 in (0..m)
      for i in (0...ysts0.length)
        dst0 = dists[y][m0][i]
        next if dst0 >= MAX_INT

        x0, d0 = ysts0[i]

        for j in (0...ysts1.length)
          x1, d1 = ysts1[j]
          dst1 = dst0 + (d0 + d1) * (x1 - x0).abs

          if (dists[y + 1][m0][j] > dst1)
            dists[y + 1][m0][j] = dst1;
          end
        end

        next if m0 == 0 || ysts2.nil?

        m1 = m0 - 1

        for j in (0...ysts2.length)
          x2, d2 = ysts2[j]
          dst2 = dst0 + (d0 + d2) * (x2 - x0).abs

          if (dists[y + 2][m1][j] > dst2)
            dists[y + 2][m1][j] = dst2;
          end
        end
      end
    end
  end

  min_gdist = MAX_INT

  for m0 in (0..m)
    gdist = dists[n - 1][m0].compact.min
    min_gdist = gdist if min_gdist > gdist
  end

  for m0 in (1..m)
    gdist = dists[n - 2][m0].compact.min
    min_gdist = gdist if min_gdist > gdist
  end

  puts min_gdist
end