### constant

MAX_INT = 1 << 30

### main

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

  stones = []
  nst = 0
  ystones = n.times.map{[]}
  max_x = 0

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

  edges1 = nst.times.map{[]}
  edges2 = nst.times.map{[]}

  for y in (0...(n - 1))
    for st0 in ystones[y]
      id0, x0, y0, d0 = st0
      for st1 in ystones[y + 1]
        id1, x1, y1, d1 = st1
        edges1[id0][id1] = (d0 + d1) * (x1 - x0).abs
      end

      next if y + 2 >= n
      for st2 in ystones[y + 2]
        id2, x2, y2, d2 = st2
        edges2[id0][id2] = (d0 + d2) * (x2 - x0).abs
      end
    end
  end
  #p edges1
  #p edges2

  min_gdist = MAX_INT
  dists = (m + 1).times.map{nst.times.map{MAX_INT}}
  visited = (m + 1).times.map{nst.times.map{false}}
  q = []

  for st0 in ystones[0]
    dists[m][st0[0]] = 0
    visited[m][st0[0]] = true
    q << [m, st0[0]]
  end

  if m > 0
    for st1 in ystones[1]
      dists[m - 1][st1[0]] = 0
    visited[m - 1][st1[0]] = true
      q << [m - 1, st1[0]]
    end
  end

  while ! q.empty?
    u = q.min{|a, b| dists[a[0]][a[1]] <=> dists[b[0]][b[1]]}
    q.delete u

    m0 = u[0]
    id0, x0, y0 = stones[u[1]]

    if y0 >= n - 1 || (m0 > 0 && y0 >= n - 2)
      gdist = dists[m0][id0]
      min_gdist = gdist if min_gdist > gdist
      next
    end

    for v in ystones[y0 + 1]
      id1, x1, y1 = v
      dv = dists[m0][id0] + edges1[id0][id1]
      if dists[m0][id1] > dv
        dists[m0][id1] = dv
        if ! visited[m0][id1]
          visited[m0][id1] = true
          q << [m0, id1]
        end
      end
    end

    next if m0 == 0

    for v in ystones[y0 + 2]
      id2, x2, y2 = v
      m1 = m0 - 1
      dv = dists[m0][id0] + edges2[id0][id2]
      if dists[m1][id2] > dv
        dists[m1][id2] = dv
        if ! visited[m1][id2]
          visited[m1][id2] = true
          q << [m1, id2]
        end
      end
    end
  end

  puts min_gdist
end