#include <bits/stdc++.h>
using namespace std;
const int N = 50, M = 5e3, K = 2501;
int n,m,a[N],b[N],w[N][N],f[N][M<<1],ans;
int main() {
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; i++) scanf("%d%d",&a[i],&b[i]);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d",&w[i][j]);
    memset(f,0xaf,sizeof(f));
    f[0][K] = 0;
    for (int i=1; i<=n; i++) for (int j=a[i]; j<M+K; j++) for (int k=0; k<i; k++)
        if (f[k][j-a[i]]!=f[0][0]) f[i][j]=max(f[i][j],f[k][j-a[i]]+b[i]+w[k][i]);
    ans = f[0][0];
    for (int i = 0; i <= n; i++) ans = max(ans,f[i][m+K]);
    if (ans == f[0][0]) printf("-1\n");
    else printf("%d\n",ans);
    return 0;
}