Siruseri城中的道路都是单向的。不同的道路由路口连接。按照法律的规定,在每个路口都设立了一个Siruseri银行的ATM取款机。令人奇怪的是,Siruseri的酒吧也都设在路口,虽然并不是每个路口都设有酒吧。 Banditji计划实施Siruseri有史以来最惊天动地的ATM抢劫。他将从市中心出发,沿着单向道路行驶,抢劫所有他途径的ATM机,最终他将在一个酒吧庆祝他的胜利。 使用高超的黑客技术,他获知了每个ATM机中可以掠取的现金数额。他希望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可以经过同一路口或道路任意多次。但只要他抢劫过某个ATM机后,该ATM机里面就不会再有钱了。 例如,假设该城中有6个路口,道路的连接情况如下图所示:
市中心在路口1,由一个入口符号→来标识,那些有酒吧的路口用双圈来表示。每个ATM机中可取的钱数标在了路口的上方。在这个例子中,Banditji能抢劫的现金总数为47,实施的抢劫路线是:1-2-4-1-2-3-5。
50%的输入保证N, M<=3000。所有的输入保证N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。