ぴょんぴょん川渡り

0530.cpp

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i, n) for (int i = 0; i < n; i++)
#define fi first
#define se second

const int inf = 1e17 + 9;

typedef pair<int, int> P;

int n, m;
int k[160];

int dp[160][16][80];

signed main()
{
  while (cin >> n >> m, n){
    vector<P> s[160];
    rep(i, n){
      cin >> k[i];
      rep(j, k[i]){
        int d, x;
        cin >> x >> d;
        s[i].push_back(P(x, d));
      }
    }

    rep(i, 160) rep(j, 16) rep(l, 80) dp[i][j][l] = inf;

    rep(j, k[0]) dp[0][j][m] = 0;
    if (m) rep(j, k[1]) dp[1][j][m - 1] = 0;

    rep(i, n - 1){
      rep(j, k[i]){
        rep(l, m + 1){
          if (i == n - 2 && l > 0) continue;

          rep(t, k[i + 1]){
            int cost = (s[i][j].se + s[i + 1][t].se) * abs(s[i][j].fi - s[i + 1][t].fi);
            dp[i + 1][t][l] = min(dp[i + 1][t][l], dp[i][j][l] + cost);
          }

          if (l > 0){
            rep(t, k[i + 2]){
              int cost = (s[i][j].se + s[i + 2][t].se) * abs(s[i][j].fi - s[i + 2][t].fi);
              dp[i + 2][t][l - 1] = min(dp[i + 2][t][l - 1], dp[i][j][l] + cost);
            }
          }
        }
      }
    }

    int ans = inf;
    rep(j, k[n - 1]) rep(l, m + 1) ans = min(ans, dp[n - 1][j][l]);
    rep(j, k[n - 2]) for (int l = 1; l <= m; l++) ans = min(ans, dp[n - 2][j][l]);

    cout << ans << endl;
  }
}