Pony.ai 有N个office分布在不同地方(编号从0开始），某些office之间有部署专线，office之间可以通过专线间接连接（专线是双向的），例如guagnzhou和beijing之间有专线，guagnzhou和shenzhen之间有专线，那么beijing可以通过guangzhou与shenzhen间接地通讯，这条信路的总延时是两条专线的延时之和。两个office之间的通讯延时是他们之间延时最短的信路的延时。 Infra团队知道当前任意两个office之间的通讯延时。最近Infra团队希望在office a与 office b之间部署一条新的专线，希望这条专线的延时 t 尽可能大（出于成本考虑）同时延时最大的两个office之间的通讯延时与 t 之和小于k，你能帮忙求出这个 t 吗？

输入描述:

第一行一个正整数 N 接下来N行，每行N个非负整数，用空格分开。第i行第j个数表示当前office i和office j之间的通讯延时，保证小于1e9。接下来一行3个整数，依次表示a，b，k。其中 。

输出描述:

输出一行一个整数，满足条件的t，注意t不能是负数。如果不存在满足条件的t，输出 -1。