/*
S:当前已经在联通块中的所有点的集合
1. dist[i] = inf
2. for n 次
    t<-S外离S最近的点
    利用t更新S外点到S的距离
    st[t] = true
n次迭代之后所有点都已加入到S中
联系：Dijkstra算法是更新到起始点的距离，Prim是更新到集合S的距离
*/
#include<iostream>
#include<cstring>
using namespace std;
const int N=550;
const int INF=0x3f3f3f3f;
int n,m;
int g[N][N];//储存边
int dist[N];//储存到集合的距离
bool st[N];//判断是否收到集合里了
int prim(){
    int res=0;//储存最小数的权值
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;//定点出发也不用特判两个
    // 因为有n个点所以要迭代n次
    for(int i=0;i<n;i++){
        int t=-1;//储存离集合最近的点的编号以及初始判断
        for(int j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dist[t]>dist[j])){
                t=j;
            }
        }
        if(dist[t]==INF){
            return INF;
        }
        res+=dist[t];
        // 吸收进来t要更新st[t]
        st[t]=1;
        // 更新其他的距离,集合里面的被更新了也无所谓因为接下来也用不到了
        // 用min来更新是比较由新点更新的还是以前的点更新的，记录路径就在这里做文章了
        for(int j=1;j<=n;j++){
            dist[j]=min(dist[j],g[t][j]);
        }
    }
    return res;
}
int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof g);//初始化图
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=g[b][a]=min(g[a][b],c);//防止重边取最小值,并且是无向边
        // 所以同时更新两个边
    }
    int t=prim();
    if(t==INF){
        cout<<"impossible";
    }
    else{
        cout<<t;
    }
    return 0;
}

// 觉得巧妙的是察觉到天数是符合二段性的用二分查找
// 注意每次查看天的时候，f都要恢复成g数组
// 技巧，一般需要三个数组，一个保持原来样子，一个是要求，一个用于储存变化后的
// !当不能低于要求时用max来保持
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=110;
int g[N][N];
int f[N][N];
int m[N][N];
ll n,q;
// 求出返回治理后的总和
ll floy(){
    ll a=0;
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a+=f[i][j];
        }
    }
    return a;
}
// 检查经过x天是否能行
bool check(int x){
    int h=x/n;//经历h轮
    int s=x%n;//额外多的几天
    memcpy(f,g,sizeof(g));
    // 开始治理
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j){
                continue;
            }
            if(i<=s){//多一次的城市
                f[i][j]=max(m[i][j],f[i][j]-h-1);
            }
            else{
                f[i][j]=max(m[i][j],f[i][j]-h);
            }
            // 共同道路，也要更新
            f[j][i]=f[i][j];
        }
    }
    return floy()<=q;

}
void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>g[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>m[i][j];
            // 进行初始判断，因为floy里用的是f数组，这里进行赋值
            f[i][j]=m[i][j];
        }
    }
    if(floy()>q){
        cout<<"-1";
        return;
    }
    ll l=0,r=10000010;
    // 采用二分进行查找天数，如果20天能够满足，那么最少天数一定在20天内
    // 符合二段性
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    cout<<l;

}
int main(){
    solve();
    return 0;

}

// 这个题目的数据范围比较弱，ai的全部和加起来也不超过1e5就说明可以采用暴力
// 另外觉得巧妙的是用一个bool 数组来储存这个数组中哪些数是存在的
// 用的时候先判断是不是存在，存在的话就可以用，很巧妙
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
bool st[N];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        st[a[i]]=true;
    }
    for(int i=0;i<n;i++){
        bool flag=false;
        for(int j=1;j<a[i];j++){
              if(st[j]&&st[a[i]-j]){
                flag=true;
                break;
              }
        }
        if(flag){
            cout<<"Yes"<<endl;
        }
        else{
            cout<<"No"<<endl;
        }
    }
    return 0;
}

// 首先知道并查集带权的操作，需要p，d数组
// d数组储存的是到父节点的距离，不过经过find函数后，父节点变成根节点
// d储存的就是到根节点的距离了，所以a,b如果在一个并查集中
// a与b之间的距离就是d[b]-d[a]（可能会产生负值因为有方向性）
// find函数首先记录旧的父亲，然后寻找根节点，再更新自己的距离为到根节点的距离
// 合并操作时候，除了让父节点pl认pr为父亲，关键更新为
// !d[pl]=d[r]-d[l]-距离


// !另外本题让我对数组的理解更深一层，数组中的值可以看做数字之间的距离
// 比如告诉a[3]=5代表2号点到3号点距离为5
// a[3]+a[4]=5代表2号到4号距离为5 本题就可转化为告诉m条边问是否在
// 一个连通集，在的话距离为多少
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+10;
// 并查集
int p[N];
// 到根距离
ll d[N];
int n,m,q;
int find(int x){
    if(p[x]!=x){
        int t=p[x];//t储存旧的父亲
        p[x]=find(p[x]);//找到父亲
        d[x]+=d[t];//更新d[x]
    }
    return p[x];
}
int main(){
    cin>>n>>m>>q;
    // 初始化并查集
    for(int i=1;i<=n;i++){
        p[i]=i;
    }
    while(m--){
        ll l,r,s;
        cin>>l>>r>>s;
        // 找根节点 前缀和 s=sum[r]-sum[l-1]抽象为l-1到r的距离为s
        int pl=find(l-1),pr=find(r);
        // 合并
        p[pl]=pr;
        // !合并时候操作 d[r]-d[l]-（l与r之间的距离）
        d[pl]=d[r]-d[l-1]-s;
    }
    // 查询
    // 在一个联通集，就输出距离l---r =d[r]-d[l]
    while(q--){
        int l,r;
        cin>>l>>r;
        int pl=find(l-1),pr=find(r);
        if(pl!=pr){
            cout<<"UNKNOWN"<<endl;
        }
        else{
            cout<<d[r]-d[l-1]<<endl;
        }
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
    string temp = "aaabcdaaa!!!";
    int num = count(temp.begin(),temp.end(),'a');
    cout <<"在字符串" << temp << "中，" <<"字母a出现的次数是" << num << endl;
    return 0 ;
}

#include<iostream>
#include<string>
using namespace std;
int main(){
    int a=12;
    string s=to_string(a);
    cout<<s;
}

// 这个用模拟栈和贪心是小端更小的思想来求得长度
// 时间复杂度为nlogn
// lower_bound是二分，最后栈中储存的不是原本顺序的上升子序列
// 只不过长相同
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
const int N=1e5+10;
int a[N];
vector<int> stk;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    stk.push_back(a[0]);
    for(int i=1;i<=n;i++){
        if(a[i]>stk.back()){
            stk.push_back(a[i]);
        }
        else{
            *lower_bound(stk.begin(),stk.end(),a[i])=a[i];
        }
    }
    cout<<stk.size();
    return 0;

}

// 这个用模拟栈和贪心是小端更小的思想来求得长度
// 时间复杂度为nlogn
// lower_bound是二分，最后栈中储存的不是原本顺序的上升子序列
// 只不过长相同
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
const int N=1e5+10;
int a[N];
vector<int> stk;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    stk.push_back(a[0]);
    for(int i=1;i<=n;i++){
        if(a[i]>stk.back()){
            stk.push_back(a[i]);
        }
        else{
            *lower_bound(stk.begin(),stk.end(),a[i])=a[i];
        }
    }
    cout<<stk.size();
    return 0;

}

// lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

// 在从小到大的排序数组中，

// lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

// upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

// 在从大到小的排序数组中，重载lower_bound()和upper_bound()

// lower_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

// upper_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=100000+10;
const int INF=2*int(1e9)+10;
#define LL long long
int cmd(int a,int b){
    return a>b;
}
int main(){
    int num[6]={1,2,4,7,15,34}; 
    sort(num,num+6);                           //按从小到大排序 
    int pos1=lower_bound(num,num+6,7)-num;    //返回数组中第一个大于或等于被查数的值 
    int pos2=upper_bound(num,num+6,7)-num;    //返回数组中第一个大于被查数的值
    cout<<pos1<<" "<<num[pos1]<<endl;
    cout<<pos2<<" "<<num[pos2]<<endl;
    sort(num,num+6,cmd);                      //按从大到小排序
    int pos3=lower_bound(num,num+6,7,greater<int>())-num;  //返回数组中第一个小于或等于被查数的值 
    int pos4=upper_bound(num,num+6,7,greater<int>())-num;  //返回数组中第一个小于被查数的值 
    cout<<pos3<<" "<<num[pos3]<<endl;
    cout<<pos4<<" "<<num[pos4]<<endl;
    return 0;   
}