奶牛们没钱了，正在找工作。农夫约翰知道后，希望奶牛们四处转转，碰碰运气。而且他还加了一条要求：一头牛在一个城市最多只能赚 美元，然后它必须到另一座城市工作。当然，它可以在别处工作一阵后又回来原来的城市再最多赚 美元。而且这样往往返返的次数没有限制。城市间有 条单向路径连接，共有 座城市，编号 。贝希当前处在城市 。路径 从城市 到城市 ，在路径上行走不用花任何费用。为了帮助贝希，约翰让它使用他的私人飞机服务。这项服务有 条航线，每条航线是从城市 飞到另一座城市 ，费用是 美元。如果贝希手中如果没有现钱，可以用以后赚的钱来付机票钱。贝希可以选择任何时候，在任何城市退休。如果在工作时间上不作限制，贝希总共可以赚多少钱呢？如果赚的钱也不会出现限制，就输出 -1。
