众所周知，SMU算法竞赛团队存在着极其复杂的内部依赖关♂系，这个依赖关系体现在每次决定是否出去吃饭的时候。某个周六中午，大家相约一起去吃自助，却忘记叫队长一起去了。下午训练结束了到了吃饭的时间，队长问大家一句：吃饭吗？大家刚吃完自助很饱，其实都不想去，但是又不好意思直接说出口，于是开始耍花招：磊子哥说，杰去我就去；琛说，佳佳文去我就去；玮说，琛去我就去……

    为了不让队长生气，每个人至多只能依赖一个人，但是一个人可以被多个人依赖。

    在队长的心里，和每个人去吃饭都有一个期待值，一个人和队长一起去吃饭了，队长就能得到对应的期待值。而劝导一个人去吃饭会有一定的花费，比如杰是一个富 有 原 则 性的人，除非你给他5元或5元以上的钱，否则他是绝对不会一起去的。现在队长有S元钱，告诉你队长对于每个人的期待值以及劝导他去吃饭的最小花费，队长想知道在花费不超过S元的前提下，他能获得的最大期待值。值得注意的是，队长要劝导一个人去吃饭，必须先劝导他依赖的人去吃饭（如果有的话）。（换言之，u依赖v，要劝导u去吃饭，必须先劝导v）。另外，如果依赖关系构成了一个环（比如1依赖2,2依赖3,3依赖1），队长会感觉自己受到了侮辱，所以不会劝导这个环的任何一个人。