#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

#define MAXN 3010

const int INF = 2e9;

int i,j,a,c,k,x,n,m;

vector< pair<int,int> > e[MAXN];

int size[MAXN],f[MAXN][MAXN];

inline void dfs(int x)

{

        int i,j,k,y,cost;

        for (i = ; i < e[x].size(); i++)

        {

                y = e[x][i].first;

                cost = e[x][i].second;

                dfs(y);

                size[x] += size[y];

                for (j = size[x]; j >= ; j--)

                {

                        for (k = ; k <= size[y]; k++)

                        {

                                if (j >= k && f[x][j-k] != -INF && f[y][k] != -INF)

                                        f[x][j] = max(f[x][j],f[x][j-k]+f[y][k]-cost);

                        }

                }

        }

}

int main()

{

        scanf("%d%d",&n,&m);

        for (i = ; i <= n; i++)

        {

                for (j = ; j <= m; j++)

                {

                        f[i][j] = -INF;

                }

        }

        for (i = ; i <= n - m; i++)

        {

                scanf("%d",&k);

                for (j = ; j <= k; j++)

                {

                        scanf("%d%d",&a,&c);

                        e[i].push_back(make_pair(a,c));

                }

        }

        for (i = n - m + ; i <= n; i++)

        {

                scanf("%d",&x);

                size[i] = ;

                f[i][] = x;

        }

        dfs();

        for (i = m; i >= ; i--)

        {

                if (f[][i] >= )

                {

                        printf("%d\n",i);

                        break;

                }

        }

        return ;

}