#include <map>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <algorithm>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

inline int getInt(){ int s; scanf("%d", &s); return s; }

using namespace std;

int main(){
  while(true){
    int n = getInt();
    int m = getInt();

    if(n + m == 0) break;

    vector<map<int, int> > v(n);

    REP(i,n){
      const int k = getInt();
      REP(j,k){
        const int x = getInt();
        const int d = getInt();
        v[i][x] = d;
      }
    }

    vector<vector<map<int, int> > >
      dp(n, vector<map<int, int> >(m + 1));

    FOR(it, v[0]){
      dp[0][m][it->first] = 0;
    }

    if(m > 0){
      FOR(it, v[1]){
        dp[1][m - 1][it->first] = 0;
      }
    }

    REP(i, n - 1) REP(j, m + 1) FOR(it1, dp[i][j]){
      // printf("(%d, %d) %d => %d\n", it1->first, i, j, it1->second);

      FOR(it2, v[i + 1]){
        const int x1   = it1->first;
        const int x2   = it2->first;
        const int cost = (v[i][it1->first] + it2->second) * std::abs(x1 - x2);
        const int next = it1->second + cost;

        // printf(" (%d, %d) %d: %d\n", x2, i + 1, j, next);

        if(dp[i + 1][j].count(x2))
          dp[i + 1][j][x2] = min(dp[i + 1][j][x2], next);
        else
          dp[i + 1][j][x2] = next;
      }
      if(j != 0 && i != n - 2){
        FOR(it2, v[i + 2]){
          const int x1   = it1->first;
          const int x2   = it2->first;
          const int cost = (v[i][it1->first] + it2->second) * std::abs(x1 - x2);
          const int next = it1->second + cost;

          // printf(" (%d, %d) %d: %d\n", x2, i + 2, j - 1, next);

          if(dp[i + 2][j - 1].count(x2))
            dp[i + 2][j - 1][x2] = min(dp[i + 2][j - 1][x2], next);
          else
            dp[i + 2][j - 1][x2] = next;
        }
      }
    }

    int ans = INT_MAX;

    REP(j,m + 1)FOR(it,dp[n - 1][j]){
      ans = min(ans, it->second);
    }
    REP(j,m)FOR(it,dp[n - 2][j + 1]){
      ans = min(ans, it->second);
    }

    printf("%d\n", ans);
  }
  return 0;
}