Buggy python submission (verdict: Time Limit Exceeded):
"""
nodes
0 ... start
k*num + 1 ~ (k+1)*num ... j=k (k <= m)
num * (m + 1) + 1 ... end
"""
from heapq import heappush, heappop
INF = 10 ** 20
while True:
  n, m = map(int, input().split())
  if n == 0:
    break
  lines = []
  klst = []
  acc = 1
  for _ in range(n):
    lst = list(map(int, input().split()))
    k = lst[0]
    klst.append(k)
    line = []
    for i in range(k):
      line.append((acc, lst[i * 2 + 1], lst[i * 2 + 2]))
      acc += 1
    lines.append(line)

  num = sum(klst)
  edges = [[] for _ in range(num * (m + 1) + 2)]

  for i in range(n - 1):
    line1 = lines[i]
    line2 = lines[i + 1]
    for acc1, x1, d1 in line1:
      for acc2, x2, d2 in line2:
        for j in range(m + 1):
          edges[acc1 + num * j].append((acc2 + num * j, (d1 + d2) * abs(x1 - x2)))
  
  for i in range(n - 2):
    line1 = lines[i]
    line2 = lines[i + 2]
    for acc1, x1, d1 in line1:
      for acc2, x2, d2 in line2:
        for j in range(m):
          edges[acc1 + num * j].append((acc2 + num * (j + 1), (d1 + d2) * abs(x1 - x2)))

  for acc, x, d in lines[0]:
    edges[0].append((acc, 0))
  if m >= 1:
    for acc, x, d in lines[1]:
      edges[0].append((acc + num, 0))
  for acc, x, d in lines[-1]:
    for j in range(m + 1):
      edges[acc + num * j].append((num * (m + 1) + 1, 0))
  for acc, x, d in lines[-2]:
    for j in range(m):
      edges[acc + num * j].append((num * (m + 1) + 1, 0))

  que = []
  heappush(que, (0, 0))
  costs = [INF] * (num * (m + 1) + 2)
  costs[0] = 0
  while que:
    total, node = heappop(que)
    for to, cost in edges[node]:
      if costs[to] > total + cost:
        costs[to] = total + cost
        heappush(que, (total + cost, to))
  print(costs[num * (m + 1) + 1])



Fixed submission:
"""
nodes
0 ... start
k*num + 1 ~ (k+1)*num ... j=k (k <= m)
num * (m + 1) + 1 ... end
"""
from heapq import heappush, heappop
def main():
  INF = 10 ** 20
  while True:
    n, m = map(int, input().split())
    if n == 0:
      break
    lines = []
    acc = 1
    for _ in range(n):
      lst = list(map(int, input().split()))
      k = lst[0]
      line = [(acc + i, lst[i * 2 + 1], lst[i * 2 + 2]) for i in range(k)]
      acc += k
      lines.append(line)
  
    num = acc - 1
    edges = [[] for _ in range(num * (m + 1) + 2)]
    for line1, line2 in zip(lines, lines[1:]):  
      for acc1, x1, d1 in line1:
        for acc2, x2, d2 in line2:
          cost = (d1 + d2) * abs(x1 - x2)
          n1 = acc1
          n2 = acc2
          for j in range(m + 1):
            edges[n1].append((n2, cost))
            n1 += num
            n2 += num
    
    for line1, line2 in zip(lines, lines[2:]):  
      for acc1, x1, d1 in line1:
        for acc2, x2, d2 in line2:
          cost = (d1 + d2) * abs(x1 - x2)
          n1 = acc1
          n2 = acc2 + num
          for j in range(m):
            edges[n1].append((n2, cost))
            n1 += num
            n2 += num
  
    for acc, _, _ in lines[0]:
      edges[0].append((acc, 0))
    if m >= 1:
      for acc, _, _ in lines[1]:
        edges[0].append((acc + num, 0))

    end = num * (m + 1) + 1
    for acc, _, _ in lines[-1]:
      b = acc
      for j in range(m + 1):
        edges[b].append((end, 0))
        b += num
    for acc, _, _ in lines[-2]:
      b = acc
      for j in range(m):
        edges[b].append((end, 0))
        b += num
    
    def search():
      que = []
      heappush(que, (0, 0))
      costs = [INF] * (num * (m + 1) + 2)
      costs[0] = 0
      while que:
        total, node = heappop(que)
        for to, cost in edges[node]:
          new_total = total + cost
          if to == end:
            print(new_total)
            return
          if costs[to] > new_total:
            costs[to] = new_total
            heappush(que, (new_total, to))
    search()
main()

Buggy python submission (verdict: Time Limit Exceeded):
"""
nodes
0 ... start
k*num + 1 ~ (k+1)*num ... j=k (k <= m)
num * (m + 1) + 1 ... end
"""
from heapq import heappush, heappop
def main():
  INF = 10 ** 20
  while True:
    n, m = map(int, input().split())
    if n == 0:
      break
    lines = []
    acc = 1
    for _ in range(n):
      lst = list(map(int, input().split()))
      k = lst[0]
      line = []
      for i in range(k):
        line.append((acc, lst[i * 2 + 1], lst[i * 2 + 2]))
        acc += 1
      lines.append(line)
  
    num = acc - 1
    edges = [[] for _ in range(num * (m + 1) + 2)]
  
    for i in range(n - 1):
      line1 = lines[i]
      line2 = lines[i + 1]
      for acc1, x1, d1 in line1:
        for acc2, x2, d2 in line2:
          for j in range(m + 1):
            edges[acc1 + num * j].append((acc2 + num * j, (d1 + d2) * abs(x1 - x2)))
    
    for i in range(n - 2):
      line1 = lines[i]
      line2 = lines[i + 2]
      for acc1, x1, d1 in line1:
        for acc2, x2, d2 in line2:
          for j in range(m):
            edges[acc1 + num * j].append((acc2 + num * (j + 1), (d1 + d2) * abs(x1 - x2)))
  
    for acc, x, d in lines[0]:
      edges[0].append((acc, 0))
    if m >= 1:
      for acc, x, d in lines[1]:
        edges[0].append((acc + num, 0))
    for acc, x, d in lines[-1]:
      for j in range(m + 1):
        edges[acc + num * j].append((num * (m + 1) + 1, 0))
    for acc, x, d in lines[-2]:
      for j in range(m):
        edges[acc + num * j].append((num * (m + 1) + 1, 0))
  
    que = []
    heappush(que, (0, 0))
    costs = [INF] * (num * (m + 1) + 2)
    costs[0] = 0
    while que:
      total, node = heappop(que)
      for to, cost in edges[node]:
        new_total = total + cost
        if costs[to] > new_total:
          costs[to] = new_total
          heappush(que, (new_total, to))
    print(costs[num * (m + 1) + 1])
main() 


Fixed submission:
"""
nodes
0 ... start
k*num + 1 ~ (k+1)*num ... j=k (k <= m)
num * (m + 1) + 1 ... end
"""
from heapq import heappush, heappop
def main():
  INF = 10 ** 20
  while True:
    n, m = map(int, input().split())
    if n == 0:
      break
    lines = []
    acc = 1
    for _ in range(n):
      lst = list(map(int, input().split()))
      k = lst[0]
      line = [(acc + i, lst[i * 2 + 1], lst[i * 2 + 2]) for i in range(k)]
      acc += k
      lines.append(line)
  
    num = acc - 1
    edges = [[] for _ in range(num * (m + 1) + 2)]
    for line1, line2 in zip(lines, lines[1:]):  
      for acc1, x1, d1 in line1:
        for acc2, x2, d2 in line2:
          cost = (d1 + d2) * abs(x1 - x2)
          n1 = acc1
          n2 = acc2
          for j in range(m + 1):
            edges[n1].append((n2, cost))
            n1 += num
            n2 += num
    
    for line1, line2 in zip(lines, lines[2:]):  
      for acc1, x1, d1 in line1:
        for acc2, x2, d2 in line2:
          cost = (d1 + d2) * abs(x1 - x2)
          n1 = acc1
          n2 = acc2 + num
          for j in range(m):
            edges[n1].append((n2, cost))
            n1 += num
            n2 += num
  
    for acc, _, _ in lines[0]:
      edges[0].append((acc, 0))
    if m >= 1:
      for acc, _, _ in lines[1]:
        edges[0].append((acc + num, 0))

    end = num * (m + 1) + 1
    for acc, _, _ in lines[-1]:
      b = acc
      for j in range(m + 1):
        edges[b].append((end, 0))
        b += num
    for acc, _, _ in lines[-2]:
      b = acc
      for j in range(m):
        edges[b].append((end, 0))
        b += num
    
    def search():
      que = []
      heappush(que, (0, 0))
      costs = [INF] * (num * (m + 1) + 2)
      costs[0] = 0
      while que:
        total, node = heappop(que)
        for to, cost in edges[node]:
          new_total = total + cost
          if to == end:
            print(new_total)
            return
          if costs[to] > new_total:
            costs[to] = new_total
            heappush(que, (new_total, to))
    search()
main()